题目
如图所示，有一个6 * 6的迷宫，左上角为入口，右下角为出口。图中0的位置可以走，1的位置不能走。请编程找出唯一的一条通过迷宫的路。
解题思路
想到了一个不太正经的解题思路
遍历所有的点，检查这些点周围路径的数量（也就是零的数量）。如果这个点周围路径只有一条，说明这是条死路，那我们用1替代了 0，这样编历几遍之后（我也无法计算需要遍历几遍，像这个简单的迷宫只需遍历两遍）数组就会只剩下一条0组成由入口到出口的通路。
最后用递归把迷宫的文字走法打印出来。
源码
(先看打印结果再读源码会容易理解些)
#include <stdio.h>
#define MAXSIZE 6
void printMaze(int maze[][MAXSIZE]);//打印当前迷宫
int countWay(int maze[][MAXSIZE], int x, int j);//计算这个点能走的方向数
void checkThePiont(int maze[][MAXSIZE], int x, int j);//检测这个路是否死路，死路就封掉
void findTheWay(int maze[][MAXSIZE], int x, int y);//用文字打印迷宫路径
void main()
{
int i, j, k;
int maze[MAXSIZE][MAXSIZE] =
{
{ 0,1,0,1,1,1 },
{ 0,0,0,1,0,1 },
{ 0,1,1,0,0,0 },
{ 0,1,1,0,1,0 },
{ 0,0,0,0,1,0 },
{ 0,1,1,1,1,0 }
};
printf("迷宫\n");
printMaze(maze);//打印迷宫
for (k = 0; k < 2; k++)//遍历迷宫次数K
{
for (i = 0; i < MAXSIZE; i++)
{
for (j = 0; j < MAXSIZE; j++)
{
if(maze[i][j]!=1)//如果这个点不是1，我们就检查它
{
checkThePiont(maze, i, j);//把能走的方向数为一的点封掉
}
}
}
}
printf("迷宫路径地图\n");
printMaze(maze);
printf("\n\n迷宫路径指导\n");
findTheWay(maze, 0, 0);//文字打印迷宫走法
getchar();
}
int countWay(int maze[][MAXSIZE], int x, int y)//统计某点能走的方向数
{
int wayNum = 0;
if (maze[x + 1][y] == 0 && x != MAXSIZE - 1)
{
wayNum += 1;
}
if (maze[x - 1][y] == 0 && x != 0)
{
wayNum += 1;
}
if (maze[x][y + 1] == 0 && y != MAXSIZE - 1)
{
wayNum += 1;
}
if (maze[x][y - 1] == 0 && y != 0)
{
wayNum += 1;
}
return wayNum;
}
void checkThePiont(int maze[][MAXSIZE], int x, int y)
{
int wayNumber;
wayNumber = countWay(maze, x, y);//能走的方向数
if (wayNumber == 1)
{
if (x != 0 || y != 0)//防止封掉入口
{
if (x != MAXSIZE - 1 || y != MAXSIZE - 1)//防止封掉出口
{
maze[x][y] = 1;//封掉这个点
}
}
}
}
void printMaze(int maze[][MAXSIZE])//打印当前迷宫
{
int i, j;
for (i = 0; i < MAXSIZE; i++)
{
for (j = 0; j < MAXSIZE; j++)
{
printf("%d", maze[i][j]);
}
printf("\n");
}
}
void findTheWay(int maze[][MAXSIZE], int x, int y)//递归方法用文字打印点（x，y）到出口的方法，前提是只有一条路
{
printf("maze[%d][%d]",x,y);//打印出我们现在所在的点
maze[x][y] = 1;//迷宫已经简化了，所以我们不会走回头路，封掉我们走过的点
if (maze[x + 1][y] == 0 && x != MAXSIZE - 1)//寻找一下能走的方向，这个方向只有一个
{
printf("->");
findTheWay(maze, x + 1, y);
}
else if (maze[x - 1][y] == 0 && x != 0)
{
printf("->");
findTheWay(maze, x - 1, y);
}
else if (maze[x][y + 1] == 0 && y != MAXSIZE - 1)
{
printf("->");
findTheWay(maze, x, y + 1);
}
else if (maze[x][y - 1] == 0 && y != 0)
{
printf("->");
findTheWay(maze, x, y - 1);
}
else if(x == MAXSIZE - 1 && y == MAXSIZE - 1)//走到出口了
{
printf("\n嘿，我们走出来了!");
}
else
{
printf("\n糟糕，我们好像迷路了...");
}
}
执行结果
这是迷宫.PNG
总结
真想不出来如何穷举来解啊！
这个解法有两个bug
bug1.如果迷宫中有个矩形的空地或者比较宽的路(宽度大于2)的话，就会有可能陷入空地里出不来了
ヾ(´A｀)ノﾟ
当然这个bug也能解决，我们在checkaThePoint()函数里加一个功能，检查4个方向都能走的点，堵上这种点就行了。这样有些情况下会多走几步路(不会多很多)，但依然能走出去。这个简单的迷宫就不用加这个功能了。
bug2.如果有多条支路能通向出口，且支路汇率点相同，(如下图情况)就可能会陷入这种支路把自己堵死里面。出现这种情况就很麻烦，它会和bug1重合(汇聚点也属于4个方向都能走的点)，这种点又不能堵住。解决办法是标记这种点作为可以走很多次的点…这个实现上因为要和bug1区分开来就很麻烦。
图片发自简书App
如果用“栈”来思考迷宫真的是特别合适，创建一个栈来存储走过的路径，遇到岔路口时随便选一条路走，如果这条路走不通退栈到岔路口点，换条路至到走到出口点。
不要拘泥于一种思路，换一种心情去观察题目，从源头出发。
