题源
490.迷宫
505.迷宫2
499.迷宫3
三道迷宫题，围绕一个小球展开一连串复杂的故事。非常有必要精心研究这三道题。
这三道题代表了DFS、BFS、最短路径、容器、排序、存储数据结构等多个算法设计，如果是用C++编程，还会涉及到二维vector、哈希表、集合、队列等多个STL库API的应用。对于初级STL的开发人员会有很大的提升，可以深入体会到DFS、BFS与STL的一些套路。
初见迷宫---第一道题
题目描述
ps:我购买了VIP，获得了三道迷宫题的运行、调试、测试机会，物超所值。
由空地和墙组成的迷宫中有一个球。球可以向上下左右四个方向滚动，但在遇到墙壁前不会停止滚动。当球停下时，可以选择下一个方向。
给定球的起始位置，目的地和迷宫，判断球能否在目的地停下。
迷宫由一个0和1的二维数组表示。 1表示墙壁，0表示空地。你可以假定迷宫的边缘都是墙壁。起始位置和目的地的坐标通过行号和列号给出。
示例 1:
输入 1: 迷宫由以下二维数组表示
0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 0 1 1
0 0 0 0 0
输入 2: 起始位置坐标 (rowStart, colStart) = (0, 4)
输入 3: 目的地坐标 (rowDest, colDest) = (4, 4)
输出: true
解析: 一个可能的路径是 : 左 -> 下 -> 左 -> 下 -> 右 -> 下 -> 右。
示例 2:
输入 1: 迷宫由以下二维数组表示
0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 0 1 1
0 0 0 0 0
输入 2: 起始位置坐标 (rowStart, colStart) = (0, 4)
输入 3: 目的地坐标 (rowDest, colDest) = (3, 2)
输出: false
解析: 没有能够使球停在目的地的路径。
注意:
迷宫中只有一个球和一个目的地。
球和目的地都在空地上，且初始时它们不在同一位置。
给定的迷宫不包括边界 (如图中的红色矩形), 但你可以假设迷宫的边缘都是墙壁。
迷宫至少包括2块空地，行数和列数均不超过100。
题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/the-maze
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
看完题目，基本可以确认该题可以采用DFS或BFS求解。
对于搜索，我自己总结了一下几个思考步骤，这几个步骤并不涉及DFS和BFS算法本身，只是对思考一个搜索问题的脑路：
Q1，递增逻辑。既然是搜索，那“下一步”这个动作是什么”？
Q2，终止条件。搜索必须要确定合理的成功返回条件，除了考虑到主题逻辑，还需要考虑corner case。
Q3，每一次搜索需要具体处理的逻辑。
Q4，剪枝，通常也称之为“分支界限”
Q5，深搜合适还是广搜？如果选择错误，可能出现部分场景超时，应当选择一个搜索过程中重复操作最少的。通常广搜的重复操作次数要小于深搜。如果采用深搜，需要合理设计函数入参和返回值，要避免出现爆栈。
Q6，搜索过程的数据应当采用什么样的数据结构存储。过程数据可能需要持续保存，那么必须选择合适的数据结构，减少开销和重复操作。
Q7，完成搜索后，如何找到满足条件的值？
Q8：corner case设计。
针对上面几个问题，对上题对号入座。
A1：为已经停止的小球选择一个新的方向，可能为“上下左右”四个方向的某几个或者全部，具体看算法设计部分。如果不考虑算法优化，通常暴力方法是全都搜一遍。
A2：当小球停止不可以再挪动。如果小球的四个方向，被墙壁（包含边界）或者已经访问过的空地包围，无路可走，到了死胡同，则终止本轮搜索。判断是否为目标点，如果是目标点则结束全部搜索。
A3：按照该方向的指示，一直走到头，走到死胡同。然后判断是否满足A1或A2条件。
A4：已经访问过得节点不在访问，这个是比较常理的。同时，我按照很直观的逻辑想了一下，小球至少不应该再走回头路。如果他是从左\右边来的，就应该去上\下。如果是上\下来的，就应该去左\右。这样可以减少两个方向的搜索。
A5：由于只需要找到一条可能路径。简单理解就是深搜一股脑走到底，可能一次搜索就找到解。而广搜磨磨唧唧一圈一圈的扩大范围，则必须要最后才得到解。所以对于上述题目来讲，两者孰好孰坏是与case相关的。具体的算法复杂度，广搜的是时间复杂度O(m * n * Max(m,n))，空间复杂度O(mn)，DFS由于涉及到递归实现，所以复杂度我不会算了。。
A6：
首先要存储四个方向我采用vector。
其次，需要存储已经访问过得节点，避免死循环（这里不包括走过的节点，只有死胡同，也就是空白地方是可以来回走的，但是死胡同只去一次。当时我在这里费了非常大的功夫，一开始觉得如果走过的点都标记，那么会因为一个错误的解搜索而限制了该路径上的点被再次访问，以至于无法得到正确的解）
A7：用返回值来代表是否成功找到一条路径，一旦找到一条路径，全部搜索结束。
A8：按照题意，已经明确了输入输出，初步看来不存在corner case的情况。
代码
class Solution {
public:
int row;
int col;
int DfSearch(int x, int y , vector<vector<int>>& maze, vector<int>& destination,vector<vector<int>> &visited ,int dir)
{
visited[x][y] = 1;
//找到该方向上的死胡同点
while(1) {
int next_i = x + direction[dir][0];
int next_j = y + direction[dir][1];
if (next_i < 0 || next_i == maze.size() || next_j < 0 || next_j == maze[0].size() || maze[next_i][next_j] == 1) {
break;
}
x = next_i;
y = next_j;
}
if (visited[x][y] == 1) return false;
if (x == destination[0] && y == destination[1]) {
return true;
}
int flag;
// 搜索不走回头路
if (dir == 0 || dir == 1) {
flag = DfSearch(x, y, maze, destination, visited,2);
if(flag == 1) return flag;
flag = DfSearch(x, y, maze, destination,visited, 3);
if(flag == 1) return flag;
}
else {
flag = DfSearch(x, y, maze, destination, visited,0);
if(flag == 1) return flag;
flag = DfSearch(x, y, maze, destination,visited, 1);
if(flag == 1) return flag;
}
return false;
}
bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination)
{
row = maze.size();
col = maze[0].size();
vector<vector<int>> visited(row, vector<int>(col, 0)); // 存储已访问路径
int flag = 0;
//从第一个点出发时，对四个方向进行搜索
return DfSearch(start[0], start[1], maze, destination,visited,0)||
DfSearch(start[0], start[1], maze, destination,visited,1)||
DfSearch(start[0], start[1], maze, destination,visited,2)||
DfSearch(start[0], start[1], maze, destination,visited,3);
}
private:
vector<vector<int>> direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};//up down right left
};
本题还可以用BFS，但是由于后面两道题的关系，所以本题就不列举BFS的代码了。
再见迷宫，超时之殇---第二道题
题目描述
由空地和墙组成的迷宫中有一个球。球可以向上下左右四个方向滚动，但在遇到墙壁前不会停止滚动。当球停下时，可以选择下一个方向。
给定球的起始位置，目的地和迷宫，找出让球停在目的地的最短距离。距离的定义是球从起始位置（不包括）到目的地（包括）经过的空地个数。如果球无法停在目的地，返回 -1。
迷宫由一个0和1的二维数组表示。 1表示墙壁，0表示空地。你可以假定迷宫的边缘都是墙壁。起始位置和目的地的坐标通过行号和列号给出。
示例 1:
输入 1: 迷宫由以下二维数组表示
0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 0 1 1
0 0 0 0 0
输入 2: 起始位置坐标 (rowStart, colStart) = (0, 4)
输入 3: 目的地坐标 (rowDest, colDest) = (4, 4)
输出: 12
解析: 一条最短路径 : left -> down -> left -> down -> right -> down -> right。
总距离为 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12。
示例 2:
输入 1: 迷宫由以下二维数组表示
0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 0 1 1
0 0 0 0 0
输入 2: 起始位置坐标 (rowStart, colStart) = (0, 4)
输入 3: 目的地坐标 (rowDest, colDest) = (3, 2)
输出: -1
解析: 没有能够使球停在目的地的路径。
注意:
迷宫中只有一个球和一个目的地。
球和目的地都在空地上，且初始时它们不在同一位置。
给定的迷宫不包括边界 (如图中的红色矩形), 但你可以假设迷宫的边缘都是墙壁。
迷宫至少包括2块空地，行数和列数均不超过100。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/the-maze-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
题2和题1的区别在于，题1只要找到一个路径即可，题2需要找寻所有可能路径，并且返回最小步数。
按照前面的方法论，对本题对号入座。
A1：同题1。为已经停止的小球选择一个新的方向，可能为“上下左右”四个方向的某几个或者全部，具体看算法设计部分。如果不考虑算法优化，通常暴力方法是全都搜一遍。
A2：当小球停止不可以再挪动。如果小球的四个方向，被墙壁（包含边界）或者已经访问过的空地包围，无路可走，到了死胡同，则终止本轮搜索。判断是否为一个合理的解，如果是，则记录step数，并保留最小的。
A3：同题1。按照该方向的指示，一直走到头，走到死胡同。然后判断是否满足A1或A2条件。
A4：
1）已经访问过得死胡同节点不在访问，
2）如果当前已经走的步数大于了最小步数，则结束本轮搜索，提前做分支界限。
A5：由于迷宫的格子数量可能达到100*100，如果对每个死胡同做DFS，重复操作的步骤太多了。。所以稳妥之间选择BFS。
（最开始一直用DFS，前前后后改了4个多小时，做各种剪枝处理。但是，总有case超时，后面搜了题解恍然大悟，放弃DFS代码，重写BFS。。再次之前，我确实对DFS和BFS的选择不是很熟悉）
A6：
首先要存储四个方向我采用vector。同题一
其次，需要存储已经访问过的节点，讲到达该点的最小值记录在vector中。
A7：完成全部解搜索后结束，返回目标节点存储的最小step。
A8：同题一。按照题意，已经明确了输入输出，初步看来不存在corner case的情况。
总结一下，题一和题二实现上的差异。
1）完成全局搜索后返回，搜索到一个解之后依然需要继续搜索
2）始终记录最小值
代码
class Solution {
public:
int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination)
{
vector<vector<int>> visited(maze.size(), vector<int>(maze[0].size(), INT_MAX));
queue<vector<int>> q; //BFS的典型标志，先上队列
visited[start[0]][start[1]] = 0;
q.push(start);
while (!q.empty()) {
vector<int> curr = q.front();
q.pop();
vector<int> currEnd(2, 0);
//对每个点的四个方向进行搜索，可想象为二叉树的层序遍历
for (int i = 0; i < 4; ++i) {
int step = maxpath(maze, curr, i, currEnd);
if (visited[currEnd[0]][currEnd[1]] > visited[curr[0]][curr[1]] + step) {
visited[currEnd[0]][currEnd[1]] = visited[curr[0]][curr[1]] + step;
q.push(currEnd);
}
}
}
return visited[destination[0]][destination[1]] != INT_MAX ? visited[destination[0]][destination[1]] : -1;
}
private:
vector<vector<int>> direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
//获取某个方向走到死胡同的路径，并将死胡同的点作为下一次搜索的起点
int maxpath(vector<vector<int>>& maze, vector<int>& start, int dir, vector<int>& end)
{
int i = start[0];
int j = start[1];
int step = 0;
while(1) {
int next_i = i + direction[dir][0];
int next_j = j + direction[dir][1];
if (next_i < 0 || next_i == maze.size() || next_j < 0 || next_j == maze[0].size() || maze[next_i][next_j] == 1) {
break;
}
i = next_i;
j = next_j;
++step;
}
end[0] = i;
end[1] = j;
return step;
}
};
总结一下，经过题一和题二的训练和反复调试，对于DFS和BFS的应用及实现应当非常熟练了。其实题二的BFS实现，个人理解就是一个迪杰特斯拉算法。
又见迷宫，进洞不靠边--第三道题
题目描述
由空地和墙组成的迷宫中有一个球。球可以向上（u）下（d）左（l）右（r）四个方向滚动，但在遇到墙壁前不会停止滚动。当球停下时，可以选择下一个方向。迷宫中还有一个洞，当球运动经过洞时，就会掉进洞里。
给定球的起始位置，目的地和迷宫，找出让球以最短距离掉进洞里的路径。 距离的定义是球从起始位置（不包括）到目的地（包括）经过的空地个数。通过'u', 'd', 'l' 和 'r'输出球的移动方向。 由于可能有多条最短路径， 请输出字典序最小的路径。如果球无法进入洞，输出"impossible"。
迷宫由一个0和1的二维数组表示。 1表示墙壁，0表示空地。你可以假定迷宫的边缘都是墙壁。起始位置和目的地的坐标通过行号和列号给出。
示例1:
输入 1: 迷宫由以下二维数组表示
0 0 0 0 0
1 1 0 0 1
0 0 0 0 0
0 1 0 0 1
0 1 0 0 0
输入 2: 球的初始位置 (rowBall, colBall) = (4, 3)
输入 3: 洞的位置 (rowHole, colHole) = (0, 1)
输出: "lul"
解析: 有两条让球进洞的最短路径。
第一条路径是 左 -> 上 -> 左, 记为 "lul".
第二条路径是 上 -> 左, 记为 'ul'.
两条路径都具有最短距离6, 但'l' < 'u'，故第一条路径字典序更小。因此输出"lul"。
示例 2:
输入 1: 迷宫由以下二维数组表示
0 0 0 0 0
1 1 0 0 1
0 0 0 0 0
0 1 0 0 1
0 1 0 0 0
输入 2: 球的初始位置 (rowBall, colBall) = (4, 3)
输入 3: 洞的位置 (rowHole, colHole) = (3, 0)
输出: "impossible"
示例: 球无法到达洞。
注意:
迷宫中只有一个球和一个目的地。
球和洞都在空地上，且初始时它们不在同一位置。
给定的迷宫不包括边界 (如图中的红色矩形), 但你可以假设迷宫的边缘都是墙壁。
迷宫至少包括2块空地，行数和列数均不超过30。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/the-maze-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
题3和题2的区别在于
1）题2只要得到所有路径的最小步数，题3需要找寻所有可能路径的走向，并且返回字典序最小的行走方式。
2）题3中小球最终不会停到死胡同，而是在去往死胡同的路上就会掉进去。
按照前面的方法论，对本题对号入座。
A1：同题2。为已经停止的小球选择一个新的方向，可能为“上下左右”四个方向的某几个或者全部。
A2：当小球停止不可以再挪动。如果小球的四个方向，被墙壁（包含边界）或者已经访问过的空地包围，无路可走，到了死胡同，则终止本轮搜索。判断是否为一个合理的解，如果是，则记录最小步数和实际路径，并保留最小的。
A3：按照该方向的指示，一直走到头，走到死胡同。然后判断是否满足A1或A2条件。如果在走到死胡同的过程中遇到了洞，则结束本轮搜索，并在返回后记录相关路径信息（步数、走法）
A4：
1）已经访问过得死胡同节点不在访问，
2）如果当前已经走的步数大于了最小步数，则结束本轮搜索，提前做分支界限。
A5：全局搜索，依然是BFS
A6：
首先要存储四个方向我采用vector。同题一
其次，需要存储已经访问过的节点，讲到达该点的最小值记录在vector中。同题二
再次，需要一个数据结构，来记录到达每个合理点（死胡同或者洞）的最小字典序的“走法”。
（这个数据结构我尝试过N种方法，vector<vector<string>> ,unodered_map,unodered_set,最终发现unodered_map最容易理解）
A7：完成全部解搜索后结束，返回目标节点存储的“走法”。
A8：同题一。按照题意，已经明确了输入输出，初步看来不存在corner case的情况。
代码
class Solution {
public:
string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) {
string result("impossible");
vector<vector<int>> visited(maze.size(), vector<int>(maze[0].size(), INT_MAX));
unordered_map<int, string> path_table;
int table_col = maze[0].size();
queue<vector<int>> q;
vector<string> direction_tag= {"d","u","r","l"};
visited[ball[0]][ball[1]] = 0;
q.push(ball);
while (!q.empty()) {
vector<int> curr = q.front();
q.pop();
vector<int> currEnd(2, 0);
for (int i = 0; i < 4; ++i) {
int step = maxpath(maze, curr, i, hole, currEnd);
if (visited[currEnd[0]][currEnd[1]] > visited[curr[0]][curr[1]] + step) {
visited[currEnd[0]][currEnd[1]] = visited[curr[0]][curr[1]] + step;
path_table[table_col * currEnd[0] + currEnd[1]] = path_table[table_col * curr[0] + curr[1]] + direction_tag[i];
if(!(currEnd[0] == hole[0] && currEnd[1]== hole[1])){
q.push(currEnd);
}
}
if (visited[currEnd[0]][currEnd[1]] == visited[curr[0]][curr[1]] + step) {
if(path_table[table_col * currEnd[0] + currEnd[1]].compare(path_table[table_col * curr[0] + curr[1]] + direction_tag[i]) > 0){
visited[currEnd[0]][currEnd[1]] = visited[curr[0]][curr[1]] + step;
path_table[table_col * currEnd[0] + currEnd[1]] = path_table[table_col * curr[0] + curr[1]] + direction_tag[i];
if(!(currEnd[0] == hole[0] && currEnd[1]== hole[1])){
q.push(currEnd);
}
}
}
}
}
int i = visited[hole[0]][hole[1]] != INT_MAX ? visited[hole[0]][hole[1]] : -1;
if(i == -1) return result;
return path_table[table_col * hole[0] + hole[1]];
}
private:
vector<vector<int>> direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int maxpath(vector<vector<int>>& maze, vector<int>& start, int dir, vector<int>& hole,vector<int>& end) {
int i = start[0];
int j = start[1];
int step = 0;
while (1) {
int next_i = i + direction[dir][0];
int next_j = j + direction[dir][1];
if (next_i == hole[0] && next_j == hole[1])
{
end[0] = next_i;
end[1] = next_j;
step++;
return step;
}
if (next_i < 0 || next_i == maze.size() || next_j < 0 || next_j == maze[0].size() || maze[next_i][next_j] == 1){
break;
}
i = next_i;
j = next_j;
++step;
}
end[0] = i;
end[1] = j;
return step;
}
};
关于第三题，列举一个我调试1个多小时的case。
这三道题，断断续续花了我两天的时间。从题设到算法，到验证和反复调试，我相信能够彻底打通我在迷宫问题上面的任督二脉。对DFS BFS 迪杰特斯拉算法有了非常深入的理解和认知。
