/*
（一）初级迷宫问题：
0：代表通
1：代表不通
求迷宫的通路
（二）步骤：
1.创建迷宫
* 从文件中读取迷宫
* 开辟二维数组存放迷宫
2.寻找通路
* 检查某位置是否为通
* 出口位置判断
* 走过的路用2标记
* 利用栈回溯
（三）问题
1.解决回溯中重复探测：递归
2.最优解：迷宫的最短通路
*/
#include
#include
#include
#include
#define _CRT_SECURE_NO_WARNINGS 1
#define N 10
using namespace std;
struct Pos
{
size_t _row; //行
size_t _col; //列
};
void GetMap(int* m, int n)
{
int i = 0;
int j = 0;
assert(m);
FILE* fin = fopen("C:\\学习\\code\\数据结构\\MazeMap\\MazeMap.txt","r");
assert(fin);
for(i = 0; i < n; i++)
{
for(j = 0; j < n;)
{
char ch = fgetc(fin);
if(ch == '0'||ch == '1')
{
m[i*n+j] = ch - '0';
j++;
}
}
}
}
void PrintMap(int* m, int n)
{
assert(m);
int i = 0;
int j = 0;
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
cout<= 0 && next._row < n
&& next._col >= 0 && next._col < n
&& m[next._row*n+next._col] == 0)
{
return true;
}
else
{
return false;
}
}
bool SearchMazePath(int* m, int n, Pos enrty,stack paths)
{
assert(m);
paths.push(enrty);
while(!paths.empty())
{
Pos cur = paths.top();
m[cur._row * n + cur._col] = 2;
//检查是否找到出口
if(cur._row == n-1)
{
return true;
}
Pos next = cur;
//上
next._row--;
if(CheckIsAccess(m, n, next))
{
paths.push(next);
continue;
}
next = cur;
//右
next._col++;
if(CheckIsAccess(m, n, next))
{
paths.push(next);
continue;
}
next = cur; //next归位
//下
next._row++;
if(CheckIsAccess(m, n, next))
{
paths.push(next);
continue;
}
next = cur;
//左
next._col--;
if(CheckIsAccess(m, n, next))
{
paths.push(next);
continue;
}
paths.pop();
}
return false;
}
int main()
{
int map[N][N]= {0};
GetMap((int*)map, N);
PrintMap((int*)map, N);
Pos enrty = {2,0};
stack paths;
cout<
当前名称：初级版迷宫问题（栈的应用）
链接地址：http://bjjierui.cn/article/pgophi.html
