在处理迷宫问题的时候，我想起了王道机试指南上的一端文字：
深度优先搜索，它类似于人在迷宫中寻找出口：
每遇到一个路口，先往一个既定的方向走到底，直到发现出口或遇到死胡同。
发现死胡同后，就回到上一个路口，并选择另外一个方向继续寻找出口。
事实上，在处理迷宫问题时，我们也是使用这种思路。下面来介绍：
1. 问题描述
我们这样描述迷宫：设置迷宫为二维数组，数组的值为
-1：代表墙
0：代表未走过的路径
1：代表走不通的路径
2：代表路径
我们使用一个二维数组myMap[10][10]来存储本文中将要使用的迷宫：
int myMap[10][10] =
{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 0, 0,-1, 0, 0, 0,-1, 0,-1,-1, 0, 0,-1, 0, 0, 0,-1, 0,-1,-1, 0, 0, 0, 0,-1,-1, 0, 0,-1,-1, 0,-1,-1,-1, 0, 0, 0, 0,-1,-1, 0, 0, 0,-1, 0, 0, 0, 0,-1,-1, 0,-1, 0, 0, 0,-1, 0, 0,-1,-1, 0,-1,-1,-1, 0,-1,-1, 0,-1,-1,-1, 0, 0, 0, 0, 0, 0, 0,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1
};
并做出以下假设：迷宫入口为myMap[1][1],迷宫出口为myMap[8][8]。
2. 解决方案
我们尝试使用递归策略来解决问题。
首先我们使用是一个二维数组direction[4][2]，来设置搜索方向：
int direction[4][2] =
{{1,0},{-1,0},{0,1},{0,-1}
};
并按下列算法解决问题：
1. 如果当前位置为出口，结束。
2. 否则：
- 假设当前位置为路径，向某方向前进一步
- 依次遍历四个方向，若四个方向均走不通，返回上一步所在的位置（回溯）。
3. 代码
//递归解决迷宫问题#include<iostream>
#include<cstdio>using namespace std;int myMap[10][10] =
{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 0, 0,-1, 0, 0, 0,-1, 0,-1,-1, 0, 0,-1, 0, 0, 0,-1, 0,-1,-1, 0, 0, 0, 0,-1,-1, 0, 0,-1,-1, 0,-1,-1,-1, 0, 0, 0, 0,-1,-1, 0, 0, 0,-1, 0, 0, 0, 0,-1,-1, 0,-1, 0, 0, 0,-1, 0, 0,-1,-1, 0,-1,-1,-1, 0,-1,-1, 0,-1,-1,-1, 0, 0, 0, 0, 0, 0, 0,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1
};struct Point {int row;int col;Point(int x, int y) :row(x), col(y) {}
};int direction[4][2] =
{{1,0},{-1,0},{0,1},{0,-1}
};int Goal(Point cur, Point end)
{if (cur.row == end.row && cur.col == end.col){return 1;}else{myMap[cur.row][cur.col] = 2;for (int i = 0; i < 4; i++){int nx = cur.row + direction[i][0];int ny = cur.col + direction[i][1];//如果遇到障碍物if (nx < 0 || nx>9 || ny < 0 || ny>9 || (myMap[nx][ny] != 0))continue;Point t(nx, ny);if (Goal(t, end)) return 1;}myMap[cur.row][cur.col] = 1;}return 0;
}void Print()
{for (int i = 0; i < 10; i++){for (int j = 0; j < 10; j++){if (j == 9)printf("%2d", myMap[i][j]);elseprintf("%2d,", myMap[i][j]);}printf("\n");}return;
}//打印迷宫
void PrintPath()
{for (int i = 0; i < 10; i++){for (int j = 0; j < 10; j++){if (myMap[i][j] == -1) cout << "■";else if (myMap[i][j] == 2) cout << " *";else cout << "□";}cout << endl;}cout << endl;
}int main()
{Point start(1, 1);Point end(8, 8);printf("\nBefore : \n");Print();Goal(start, end);printf("\nAfter : \n");Print();printf("\nPath ：\n");PrintPath();return 0;
}
4. 拓展：使用栈来解决迷宫问题
看起来，思路好像很简单。实际上笔者花费了大半天的时间才看明白。。虽然一部分原因拜vs的逐步调试所赐。。
相比之下，使用栈来解决迷宫问题的代码相当简洁：
//栈解决迷宫问题#include<iostream>
#include<cstdio>
#include<stack>using namespace std;int myMap[10][10] =
{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 0, 0,-1, 0, 0, 0,-1, 0,-1,-1, 0, 0,-1, 0, 0, 0,-1, 0,-1,-1, 0, 0, 0, 0,-1,-1, 0, 0,-1,-1, 0,-1,-1,-1, 0, 0, 0, 0,-1,-1, 0, 0, 0,-1, 0, 0, 0, 0,-1,-1, 0,-1, 0, 0, 0,-1, 0, 0,-1,-1, 0,-1,-1,-1, 0,-1,-1, 0,-1,-1,-1, 0, 0, 0, 0, 0, 0, 0,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1
};struct Point {int row;int col;Point(int x,int y):row(x),col(y){}
};void MasePath(Point start, Point end)
{stack <Point> PointStack;Point P = start;myMap[P.row][P.col] = 2;do {PointStack.push(P);if (myMap[P.row][P.col + 1] == 0) myMap[P.row][++P.col] = 2;else if (myMap[P.row + 1][P.col] == 0) myMap[++P.row][P.col] = 2;else if (myMap[P.row][P.col - 1] == 0) myMap[P.row][--P.col] = 2;else if (myMap[P.row - 1][P.col] == 0) myMap[--P.row][P.col] = 2;else{P = PointStack.top();PointStack.pop();myMap[P.row][P.col] = 1;P = PointStack.top();PointStack.pop();}} while ((P.row != end.row) || (P.col != end.col));return;
}void Print()
{for (int i = 0; i < 10; i++){for (int j = 0; j < 10; j++){if(j==9) printf("%2d", myMap[i][j]);elseprintf("%2d,", myMap[i][j]);}printf("\n");}return;
}//打印迷宫
void PrintPath()
{for (int i = 0; i < 10; i++){for (int j = 0; j < 10; j++){if (myMap[i][j] == -1) cout << "■";else if (myMap[i][j] == 2) cout << " *";else cout << "□";}cout << endl;}cout << endl;
}int main()
{Point start(1, 1);Point end(8, 8);printf("\nBefore : \n");Print();MasePath(start, end);printf("\nAfter : \n");Print();printf("\nPath ：\n");PrintPath();return 0;
}
其解决思路类似：
1. 当前位置入栈
2. 判断下一步是否可行，
若可行 ，则返回步骤1
若不可行，则换方向继续尝试
3. 若四个方向均不可行，则当前位置出栈。回到前一个位置，换方向搜索。
5. 总结
哎呀。。迷宫问题也算是一个经典问题了
不过我只能想出来第一种递归方法，使用栈进行处理的操作还是需要进一步理解。
如果说迷宫问题的变体的话，那就是如何输出迷宫的所有可能路径呢？？？
留给以后来探索...