迷宫问题的非递归实现

2019-11-06 07:02:17

字体：大中小

来源：转载

供稿：网友

迷宫问题可以抽象为一个二维数组来求解，假设有如图示的迷宫：这里写图片描述解题思路：用一个栈来存放当前人的位置的坐标，并每次测试当前位置的上、下、左、右，看哪个位置可以继续前进，可以继续前进的位置入栈，并且将人走过的位置的值赋值为2，以此来区分在测试的是时候不会往回走，直至走进死胡同的时候，将走过的位置出栈，并再测试可以前进的位置，依次循环，直至找到出口。本例代码：

#PRagma once#include <iostream>#include <stack>using namespace std;const int N = 10;int MazeMap[N][N] ={{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },{ 0, 0, 0, 1, 1, 1, 1, 1, 1, 1 },{ 1, 1, 0, 1, 1, 1, 1, 1, 1, 1 },{ 1, 1, 0, 0, 0, 0, 0, 1, 1, 1 },{ 1, 1, 0, 1, 1, 1, 0, 1, 1, 1 },{ 1, 1, 0, 1, 1, 1, 0, 1, 1, 1 },{ 1, 1, 0, 0, 1, 1, 0, 1, 1, 1 },{ 1, 1, 1, 0, 1, 1, 0, 1, 1, 1 },{ 1, 1, 1, 0, 1, 1, 1, 1, 1, 1 },};void PrintMap(int maze[][N], size_t N) { for (size_t i = 0;i < N;++i) { for (size_t j = 0;j < N;++j) { cout << maze[i][j]<<" "; } cout << endl; }}struct Pos{ size_t i; size_t j;};bool IsGoingOn(int maze[][N], size_t N,Pos& pos){ if (maze[pos.i][pos.j ] != 0) return false; else { return true; }}void GetTheWay(int maze[][N], size_t N){ PrintMap(MazeMap,N); Pos entry = { 2,0 }; stack<Pos> sp; sp.push(entry); while (!sp.empty()) { Pos cur = sp.top(); Pos next; maze[cur.i][cur.j] = 2;//将走过的位置赋值为2，用以区分 if (cur.i == 9)//本例特殊的出口 { maze[cur.i][cur.j] = 2; cout << endl<<"finish!" << endl; break; } //右 next = cur; next.i = cur.i; next.j = cur.j + 1; if (IsGoingOn(MazeMap, N, next)) { sp.push(next); continue; } //下 next = cur; next.j = cur.j; next.i = cur.i + 1; if (IsGoingOn(MazeMap, N, next)) { sp.push(next); continue; } //上 next = cur; next.i = cur.i - 1; next.j = cur.j; if (IsGoingOn(MazeMap, N, next)) { sp.push(next); continue; } //左 next = cur; next.i = cur.i; next.j = cur.j - 1; if (IsGoingOn(MazeMap, N, next)) { sp.push(next); continue; } //出栈之前将该位置的值赋值为3 //以此来表示回溯路径 Pos back = sp.top(); maze[back.i][back.j] = 3; sp.pop(); }}void Test(){ GetTheWay(MazeMap, N); PrintMap(MazeMap, N);}

运行结果：这里写图片描述