迷宫问题是数据结构中的一个较为基本也是较为简单的问题，笔者在初学这门课时也是早早遇见了它，还是蛮有意思的，做出来的话确实给了我这种新人一点鼓励。
想法
我们小时候都玩过走迷宫，像我小时候就尤其喜欢奥特曼走迷宫【：）】。我们人脑在解决这种问题时，无外乎就是一条条的探，看那个走得通就走哪个，所以同样的，我们可以把这种思维方式模拟给计算机，让它也去尝试。当然不同的是，我们人脑有着直觉，有事可以一目十行的的看，而对于计算机，我们就需要严格的逻辑定义，让其考虑每一种可能。
基本原理
有了初步想法后，现在就来看大概实现。这个走迷宫，有点像贪吃蛇，上下左右探着走，当然，我们走迷宫，是可以返回的。依此，我们在找到了可行的通路后，将这一步所踩得点的标志位进行更改，重复这一步，若是死路则借助堆栈返回，从另一个方向开始此步骤。最终寻得最终通路，结果显示为一个二维矩阵（数组）。
代码实现
有两种实现方式，都借助了堆栈，一种是普通写法（频繁使用continue），另一种使用递归。
代码如下，注释应较为明晰。
欢迎与博主讨论。
//分别采用堆栈的方法和递归的方法对迷宫进行寻路
#include<iostream>
#include<stack>
using namespace std;
struct number //结构体方法，包含行与列数据成员
{
int row;
int col;
};
void GetMaze(int* Maze, int N) //获取迷宫信息
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
int value;
cout << "Please enter this position's value(0 & 1) : ";
cin >> value;
Maze[i * N + j] = value;
}
}
}
bool checkPath(int*Maze,int n , number path) //用于判断是否越界，同时判断该位置是否为0（0即通路）
{
if ((path.row >= 0 && path.row < 10) && (path.col >= 0 && path.col < 10) && (Maze[path.row * n + path.col] == 0))
return true;
return false;
}
void GetMazePathByStack(int* Maze, int n, number entry, stack<number>& s) //通过堆栈方式进行寻路
{
number cur = entry;
number next = cur;
Maze[cur.row * n + cur.col] = 2;
s.push(entry);
while (!s.empty())
{
if (s.top().row == n - 1)
{
return; //判断是否到达边界
}
//up
next = s.top();
next.row -= 1;
if (checkPath(Maze, n, next))
{
s.push(next);
Maze[next.row * n + next.col] = 2; //寻找通路，找到则标记为2
continue;
}
//right
next = s.top();
next.col+= 1;
if (checkPath(Maze, n, next))
{
s.push(next);
Maze[next.row * n + next.col] = 2;
continue;
}
//down
next = s.top();
next.row += 1;
if (checkPath(Maze, n, next))
{
s.push(next);
Maze[next.row * n + next.col] = 2;
continue;
}
//left
next = s.top();
next.col-= 1;
if (checkPath(Maze, n, next))
{
s.push(next);
Maze[next.row * n + next.col] = 2;
continue;
}
number noway = s.top();
Maze[noway.row * n + noway.col] = 3;
s.pop();
}
}
void GetMazePathByResursive(int* Maze, int n, number entry, stack<number>& s) //递归法寻路
{
number next = entry;
Maze[next.row * n + next.col] = 2;
s.push(entry);
if (next.row == n - 1)
{
return;
}
//up
next = entry;
next.row -= 1;
if (checkPath(Maze, n, next))
{
GetMazePathByResursive(Maze, n, next, s);
}
//right
next = entry;
next.col += 1;
if (checkPath(Maze, n, next))
{
GetMazePathByResursive(Maze, n, next, s);
}
//down
next = entry;
next.row += 1;
if (checkPath(Maze, n, next))
{
GetMazePathByResursive(Maze, n, next, s);
}
//left
next = entry;
next.col -= 1;
if (checkPath(Maze, n, next))
{
GetMazePathByResursive(Maze, n, next, s);
}
}
void printMaze(int* Maze, int n) //打印出寻路后的迷宫
{
cout << "The maze is : " << endl;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cout << Maze[i * n + j] << " ";
}
cout << endl;
}
}
int main()
{
int maze[100] = { 0 };
int n;
cout << "enter the number of the maze's col" << endl;
cin >> n;
GetMaze(maze,n);
cout << "Find path by stack way" << endl;
number start;
start.row = 0;
start.col = 0;
stack<number>a;
GetMazePathByStack(maze, n, start, a);
printMaze(maze, n);
stack<number>b;
cout << "enter the number of the maze's col" << endl;
cin >> n;
GetMaze(maze, n);
number begin;
begin.col = 0;
begin.row = 0;
cout << "Find path by recursive way" << endl;
GetMazePathByResursive(maze, n, begin, b);
printMaze(maze, n);
}