【问题描述】
以一个 m*n的方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论
其中二维矩阵中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
相关博文
c++实现源码
/*迷宫问题*/
#include<iostream>
#include<stack>
using namespace std;
char maze[10][10] =
{
{ '0','1','1','1','1','1','1','1','1','1' },
{ '0','1','0','1','1','1','1','1','1','1' },
{ '0','0','0','1','1','1','1','0','0','0' },
{ '1','0','0','0','0','1','1','0','1','0' },
{ '1','0','1','1','0','1','1','0','1','0' },
{ '1','0','1','1','0','1','1','0','1','0' },
{ '1','1','0','0','0','1','1','0','1','0' },
{ '1','1','0','1','1','1','1','0','1','0' },
{ '1','1','0','0','0','0','0','0','1','0' },
{ '1','1','1','1','1','1','1','1','1','0' },
};
/*打印源数据*/
void Show()
{
for (int i = 0; i < sizeof(maze) / sizeof(maze[0]); i++)
{
for (int j = 0; j < sizeof(maze[0]) / sizeof(maze[0][0]); j++)
{
cout << maze[i][j] << " ";
}
cout << endl;
}
}
/*递归查找*/
void RecFind(int i, int j)
{
if (maze[i][j] == '1') return;
if (maze[i][j] == '@') return;
if (maze[i][j] = '@' && j == 9 && i == 9)
{
cout << "找到路径" << endl;
Show();
exit(0);
}
maze[i][j] = '@';
RecFind(i, j + 1);
RecFind(i + 1, j);
RecFind(i, j - 1);
RecFind(i - 1, j);
}
/*非递归实现*/
void NoRecFind()
{
int i = 0;
int j = 0;
stack<char> s;
s.push(maze[i][j]);
maze[i][j] = '@';
cout << "进入方法！" << endl;
while (true)
{
if (maze[i][j + 1] == '0')
{
s.push(maze[i][++j]);
maze[i][j] = '@';
}
else if (maze[i + 1][j] == '0')
{
s.push(maze[++i][j]);
maze[i][j] = '@';
}
else if (maze[i][j - 1] == '0')
{
s.push(maze[i][--j]);
maze[i][j] = '@';
}
else if (maze[i - 1][j] == '0')
{
s.push(maze[--i][j]);
maze[i][j] = '@';
}
if (maze[i][j + 1] != '0' && maze[i + 1][j] != '0' &&
maze[i][j - 1] != '0' && maze[i - 1][j] != '0')
{
if (i >= 9 && j >= 9)
{
break;
}
else
{
maze[i][j] = '*';
s.pop();
}
char tmp = s.top();
s.push(tmp);
}
}
Show();
}
int main()
{
Show();
RecFind(0, 0);
NoRecFind();
return 0;
}
