题目

如图所示，有一个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区分开来就很麻烦。