迷宫问题，是栈的一个经典应用。在今多年的面试题中特别常见。本博主呢，也就研究了一二。
成都创新互联是一家从事企业网站建设、
成都做网站、成都网站制作、行业门户网站建设、网页设计制作的专业网络公司，拥有经验丰富的网站建设工程师和网页设计人员，具备各种规模与类型网站建设的实力，在网站建设领域树立了自己独特的设计风格。自公司成立以来曾独立设计制作的站点上千多家。
若有一迷宫，如何寻找通路？
解题思路：
迷宫，可将其看成一个二维数组。给定一个入口，需要判断此入口的上下左右是否越界，是否有通路点。若有通路点，将此点前一个通路点记录并将其置为非0（防止访问下一个通路点时再次判断）。继续寻找下一个通路,...以此类推。若查找不到通路点，则需要回溯。判断是否还有其他通路。
回溯呢，就是将从记录的通路点回退。此特征呢，和我们的栈很相似。所以，栈就在此处派上用场喽。
那么如何判断迷宫是否有通路呢？
判断条件：（1）有通路。当行或者列到达边界时即可判断。
（2）无通路。当回溯时，需要从栈中取出元素。当栈为空时即可判断。
假设有如下迷宫。（迷宫中0为通路）入口点（2,0）。
分析：
看到此迷宫，可将其看成二维数组。但是在程序中不可能一个一个输入（若迷宫很大呢）。所以可将其以文件的形式读取。我们看到在此迷宫处，有一个通路点处有两条通路，若先走下面，行到达边界处，则可直接得出有通路。若先右方，最终无通路可走，则需要回溯，在进一步的判断。当回溯到岔路口时，发现下方还有路可走。继续向下走，最终行到达边界处，即有通路。
程序实现：
"Maze.h"
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include
#include
#include
#define N 10
using namespace std;
struct Pos
{
int _row;//行
int _col;//列
};
//从文件中读出数据，并以一位数组存放
void GetMaze(int *a,int n)
{
FILE* f = fopen("test.txt","r");
assert(f);
for(int i=0;i=0)&&(next._row=0)&&
(next._col& path)
{
Pos cur = entry;
path.push(cur);
while(!path.empty())
{
a[cur._row*n+cur._col] = 2;//压栈后将其置为2，防止再次访问到
if((cur._col == n-1)||(cur._row == n-1))//通路条件，行或列到达边界
{
return true;
}
//上
Pos next = cur; //将上一个通路点保存
next._row--;
if(PathIsAccess(a,n,next))//是否越界
{
cur = next;
path.push(cur);
continue;
}
//左
next = cur;
next._col--;
if(PathIsAccess(a,n,next))
{
cur = next;
path.push(cur);
continue;
}
//右
next = cur;
next._col++;
if(PathIsAccess(a,n,next))
{
cur = next;
path.push(cur);
continue;
}
//下
next = cur;
next._row++;
if(PathIsAccess(a,n,next))
{
cur = next;
path.push(cur);
continue;
}
cur = path.top();//回溯
path.pop();
}
return false;
}
void Test()
{
int a[N][N] = {};
GetMaze((int *)a,N);
PrintMaze((int *)a,N);
stack path;
Pos entry = {2,0};
bool ret = MazePath((int *)a,N,entry,path);
cout<<"是否有通路"<测试结果：
（1）先走右方（出现回溯）
（2）先走下方
创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。
网站标题：栈---解决迷宫问题-创新互联
分享地址：http://www.cdkjz.cn/article/iedpc.html
