我们看下面这个迷宫----方阵（也可以是矩阵）：
10年积累的
网站制作、成都网站建设经验，可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你，你也不认识我。但先
做网站设计后付款的网站建设流程，更有
西华免费网站建设让你可以放心的选择与我们合作。
迷宫入口是坐标（2，0）位置，出口是（9，3）。我们假定0代表通路，1代表不通。
现在需要找到哪一条路是通路。我们的思想是借助栈，“回溯法”。回溯是什么意思呢？？？先从起点出发，检查它的上下左右是否是通路（即是否有为数字0处）。也就是说为0通了，压栈，将此位置元素变成2，这样做的好处是明确通路路径。然后继续往下走，判断上下左右 。直至我们找到终点（纵坐标在矩阵的最后一行）。
我们来看下我针对迷宫问题实现的代码：
#include
#include
#define N 10 //该迷宫10*10.
struct Pos //定义一个结构体，该结构体用来表示坐标。
{
int _row;
int _col;
Pos(int row,int col)
:_row(row)
, _col(col)
{}
};
template
bool SearchMazePath(int* a, int n, Pos entry, stack& paths) //寻找迷宫是否有通路。
{
assert(a);
paths.push(entry);
while (!paths.empty())
{
Pos cur = paths.top();
a[cur._row*n + cur._col] = 2;
if (cur._row == n - 1)
{
return true;
}
//上
Pos tmp = cur;
--tmp._row;
if (a[tmp._row*n + tmp._col] == 0)
{
paths.push(tmp);
continue;
}
//下
tmp = cur;
++tmp._row;
if (a[tmp._row*n + tmp._col] == 0)
{
paths.push(tmp);
continue;
}
//左
tmp = cur;
--tmp._col;
if (a[tmp._row*n + tmp._col] == 0)
{
paths.push(tmp);
continue;
}
//右
tmp = cur;
++tmp._col;
if (a[tmp._row*n + tmp._col] == 0)
{
paths.push(tmp);
continue;
}
paths.pop(); //若上下左右都不通，则回溯。
}
return false;
}
void GetMaze(int* a, int n) //读取到迷宫图案
{
assert(a);
FILE* fout = fopen("MazeMap.txt", "r");
assert(fout); //若文件打开失败，后续工作则无法完成，因此采用assert防御式编程。
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
while (true)
{
int men = fgetc(fout); //读取字符
if (men == '0' || men == '1') //是0或者1则转换成数字到二维矩阵中存储。
{
a[i*n + j] = men -'0';
break;
}
}
}
}
}
void PrintMaze(int* a, int n) //将此迷宫打印出来
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n;j++ )
{
cout << a[i*n + j] << " ";
}
cout << endl;
}
cout << endl;
}
void Test()
{
int a[N][N] = {};
Pos sp(2, 0); //入口坐标
GetMaze((int*) a, N);
PrintMaze((int*)a, N);
stack paths;
SearchMazePath((int*)a, N, sp, paths);
//二维数组实际存储是一维数组，将二维数组强制转换为一维数组传参。
PrintMaze((int*)a, N);
}
int main()
{
Test();
system("pause");
return 0;
}
有时候，针对迷宫问题，我们还需要求多条路径的最优解（最短路径）。那这时候我们可以用压栈，利用栈帧一层一层压栈的特点实现。
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
当前题目：【数据结构】使用栈Stack解决迷宫问题-创新互联
链接URL：
http://bjjierui.cn/article/edheh.html
