算法|迷宫搜索之深搜DFS和广搜BFS

有一天，小哈一个人去玩迷宫。但是方向感不好的小哈很快就迷路了。小哼得知后便去解救无助的小哈。此时的小哼已经弄清楚了迷宫的地图，现在小哼要以最快的速度去解救小哈。那么，问题来了...

迷宫由m行n列的单元格组成的（m和n都小于50），每个单元格要么是空地要么是障碍物，你的任务是帮小哼找到一条从迷宫的起点通往小哈所在位置的最短路径。注意障碍物是不能走的，只能上下左右走（不能斜着走），当然小哼也不能走出迷宫之外。

(迷宫问题通常用一个二维数组来表示，某一个点通常用坐标来表示，也是二维数组的下标。)

首先我们用一个二维数组来存储这个迷宫，刚开始的时候，小哼处于迷宫的入口处（1,1），小哈在（p,q）。问题的本质就在于找从（1,1）到（p,q）的最短路径。

此时摆在小哼面前的路有两条，我们可以先让小哼往右边走，直到走不通的时候再回到这里，再去尝试另外一个方向。

在这里我们规定一个顺序，按照顺时针的方向来尝试（即右→下→左→上）。

我们先来看看小哼一步之内可以到达的点有哪些？只有（1,2）和（2,1）。

根据刚才的策略，我们先往右边走，但右边（1,3）有障碍物，所以只能往下（2,2）这个点走。但是小哈并不在（2,2）这个点上，所以小哼还得继续往下走，直至无路可走或者找到小哈为止。

注意：并不是让我们找到小哈此题就解决了。因为刚才只是尝试了一条路的走法，而这条路并不一定是最短的。刚才很多地方在选择方向的时候都有多种选择，因此我们需要返回到这些地方继续尝试往别的方向走，直到把所有可能都尝试一遍，最后输出最短的一条路径。

例如下图就是一条可行的搜索路径：

1 深搜dfs

我们可以尝试用深度优先搜索来解决这个问题。

深度优先搜索需要使用到一个辅助的数据结构：栈（如果使用递归，则是由编译器来自动实现一个隐式栈），确保数据的后进先出，在图搜索时就是深度优先的搜索方式了。

1.1 dfs()函数

dfs()函数的功能是解决当前应该怎么办。而小哼处在某个点的时候需要处理的是：先检查小哼是否已经到达小哈的位置，如果没有到达则找出下一步可以走的地方。

为了解决这个问题，此处dfs()函数需要维护三个参数（通常递归函数相对于普通函数具有较多的参数，这是由递归的参数迭代关系所决定的），分别是当前这个点的x坐标，y坐标以及当前已经走过的步数step。

// dfs函数定义如下： 
void dfs(int x,int y,int step)
{
    return 0;
} 

1.2 判断是否已经到达小哈的位置

只需要判断当前的坐标是否与小哈的坐标相等就可以了，如果相等就标明已经到达小哈的位置。

void dfs(int x,int y,int step)
{
    if(x==p && y==q)  // 判断是否到达小哈的位置 
    {
        if(step<min)
            min=step;  // 更新最小值
        return;            // 这步很重要！ 
    }
    return 0;
} 

1.3 获得下一个方向的坐标（此处定义一个方向数组）

如果没有到达小哈的位置，则找出下一步可以走的地方。因为有四个方向可以走，可以定义一个方向数组next：

    int next[4][2]={
    {0,1},  // 向右走
    {1,0},  // 向下走
    {0,-1}, // 向左走
    {-1,0}, // 向上走 
    };

坐标、方向、方向数组：

通过这个方向数组，使用循环就可以方便地得到下一步的坐标。

这里将下一步的横坐标用tx存储，纵坐标用ty存储：

    for(k=0;k<=3;k++)
    {
        // 计算下一个点的坐标
        tx=x+next[k][0];
        ty=y+next[k][1];
    }

1.4 对下一个点（tx,ty）进行判断（是否越界，是否有障碍物，是否已经在路径中）

接下来我们就要对下一个点（tx,ty）进行判断，包括是否越界，是否有障碍物，是否已经在路径中（避免重复访问一个点）。需要用用book[tx][ty]来记录格子[tx][ty]是否已经在路径中。

如果这个点符合所有的要求，就对这个点进行下一步的扩展，即dfs(tx,ty,step+1)。

注意递归函数的参数迭代，此处的step+1，因为一旦从这个点开始继续往下尝试，就意味着步数已经增加了1。

    for(k=0;k<=3;k++)
    {
        // 计算下一个点的坐标
        tx=x+next[k][0];
        ty=y+next[k][1];
        if(tx<1 || tx>n || ty<1 || ty>m)  // 判断是否越界
            continue;
        // 判断该点是否为障碍物或者已经在路径中
        if(a[tx][ty]==0 && book[tx][ty]==0)
        {
            book[tx][ty]=1;     // 标记这个点已经走过
            dfs(tx,ty,step+1);  // 开始尝试下一个点
            book[tx][ty]=0;     // 尝试结束，取消这个点的标记 
        } 
    }

完整代码：

#include<stdio.h>

int n,m,p,q,min=99999999;
int a[51][51],book[51][51];

void dfs(int x,int y,int step)
{
    int next[4][2]={
        {0,1},  // 向右走
        {1,0},  // 向下走
        {0,-1}, // 向左走
        {-1,0}, // 向上走 
    };
    int tx,ty,k;
    if(x==p && y==q)  // 判断是否到达小哈的位置 
    {
        if(step<min)
            min=step; // 更新最小值
        return; 
    }
    
    for(k=0;k<=3;k++) // 枚举四种走法
    {                 // 计算下一个点的坐标
        tx=x+next[k][0];
        ty=y+next[k][1];
        if(tx<1 || tx>n || ty<1 || ty>m)  // 判断是否越界
            continue;
        // 判断该点是否为障碍物或者已经在路径中
        if(a[tx][ty]==0 && book[tx][ty]==0)
        {
            book[tx][ty]=1;     // 标记这个点已经走过
            dfs(tx,ty,step+1);  // 开始尝试下一个点
            book[tx][ty]=0;     // 尝试结束，取消这个点的标记 
        } 
    }
    return;
} 

int main()
{
    int i,j,startx,starty;
 	printf("输入迷宫行、列（直接输入，如5 4）：");
    scanf("%d %d",&n,&m);  // 读入n和m，n为行，m为列
    // 读入迷宫
	printf("输入迷宫（0表示空地，1表示障碍物）和起点、终点坐标(可一起复制)：\n");
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    scanf("%d %d %d %d",&startx,&starty,&p,&q);  // 读入起点和终点坐标
    // 从起点开始搜索
    book[startx][starty]=1; // 标记起点已经在路径中，防止后面重复走
    dfs(startx,starty,0);   // 第一个参数是起点的x坐标，以此类推是起点的y坐标，初始步数为0
    printf("%d\n",min);     // 输出最短步数
	getchar();getchar();
    return 0; 
}
/* input
5 4
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
1 1 4 3
*/
/* output
7
*/

运行效果：

第一行有两个数n m，n表示迷宫的行数，m表示迷宫的列数。

接下来n行m列为迷宫，0表示空地，1表示障碍物。

最后一行四个数，前两个数表示迷宫入口的x和y坐标，后两个为小哈的x和y坐标。

发明深度优先算法的是John E.Hopcroft 和 Robert E.Tarjan。他们并不是研究全排列或者迷宫问题时发明了这个算法。1971~1972年，他们在斯坦福大学研究图的连通性（任意两点是否可以相互到达）和平面性（图中所有的边相互不交叉。在电路板上设计布线的时候，要求线与线不能交叉，这就是平面性的一个实际应用），发明了这个算法。他们也因此获得了1986年的图灵奖。

2 广搜BFS

当然我们也可以用宽度优先搜索（BFS）来解决这个问题。

广度优先搜索需要使用到一个辅助的数据结构：队列，确保先进先出，在图搜索时，就是层层推进的广搜了。

我们还是用一个二维数组来存储这个迷宫，最开始小哼在入口（1,1）处，一步之内可以到达的点有（1,2）和（2,1）。

但是小哈并不在这两个点上，那小哼只能通过（1,2）和（2,1）这两点继续往下走。

比如现在小哼走到了（1,2）这个点，之后他又能够到达哪些新的点呢？有（2,2）。再看看通过（2,1）又可以到达哪些点呢？可以到达（2,2）和（3,1）。

此时你会发现（2,2）这个点既可以从（1,2）到达，也可以从（2,1）到达，并且都只使用了两步。

注：为了防止一个点多次被走到，这里需要一个数组来记录一个点是否已经被走到过。

此时小哼2步可以走到的点就全部走到了，有（2,2）和（3,1），可是小哈并不在这两个点上。看来没有别的办法，还得继续往下尝试，看看通过（2,2）和（3,1）这两个点还能到达哪些新的没有走到过的点。

通过（2,2）这个点我们可以到达（2,3）和（3,2），通过（3,1）可以到达（3,2）和（4,1）。

现在三步可以到达的点有（2,3）、（3,2）和（4,1），依旧没有到达小哈的所在点，所以我们需要继续重复刚才的做法，直到找到小哈所在点为止。

回顾一下刚才的算法，可以用一个队列来模拟这个过程。在这里我们用一个结构体来实现队列：

struct note{
    int x;  // 横坐标
    int y;  // 纵坐标
    int s;  // 步数 
};
struct note que[2501];  // 因为地图大小不超过50*50，因此队列扩展不会超过2500个
int head,tail;
int a[51][51] = {0};  // 用来存储地图 
int book[51][51] = {0};  // 数组book的作用是记录哪些点已经在队列中了，防止一个点被重复扩展，并全部初始化为0

// 最开始的时候需要进行队列初始化，即将队列设置为空
head = 1;
tail = 1;
// 第一步将（1,1）加入队列，并标记（1,1）已经走过。
que[tail].x = 1;
que[tail].y = 1;
que[tail].s = 0;
tail++;
book[1][1] = 1;

然后从（1,1）开始，先尝试往右走到达了（1,2）。

tx = que[head].x;
ty = que[head].y+1;

需要判断（1,2）是否越界。

if(tx < 1 || tx > n || ty < 1 || ty > m)
    continue;

再判断（1,2）是否为障碍物或者已经在路径中。

if(a[tx][ty] == 0 && book[tx][ty] == 0)
{
}

如果满足上面的条件，则将（1,2）入队，并标记该点已经走过。

book[tx][ty] = 1;  // 注意bfs每个点通常情况下只入队一次，和深搜不同，不需要将book数组还原
// 插入新的点到队列中
que[tail].x = tx;
que[tail].y = ty;
que[tail].s = que[head].s+1;  // 步数是父亲的步数+1
tail++; 

接下来还要继续尝试往其他方向走。

在这里我们规定一个顺序，即按照顺时针的方向来尝试（右→下→左→上）。

我们发现从（1,1）还是可以到达（2,1），因此也需要将（2,1）也加入队列，代码实现与刚才对（1,2）的操作是一样的。

对（1,1）扩展完毕后，此时我们将（1,1）出队（因为扩展完毕，已经没用了）。

head++;

接下来我们需要在刚才新扩展出的（1,2）和（2,1）这两个点上继续向下探索（因为还没有到达小哈所在的位置，所以还需要继续）。

（1,1）出队之后，现在队列的head正好指向了（1,2）这个点，现在我们需要通过这个点继续扩展，通过（1,2）可以到达（2,2），并将（2,2）也加入队列。

（1,2）这个点已经处理完毕，于是可以将（1,2）出队。（1,2）出队之后，head指向了（2,1）这个点。通过（2,1）可以到达（2,2）和（3,1），但是因为（2,2）已经在队列中，因此我们只需要将（3,1）入队。

到目前为止我们已经扩展出从起点出发2步以内可以到达的所有点，可是依旧没有到达小哈所在的位置，因此还需要继续扩展，直到找到小哈所在的点才算结束。

为了方便向四个方向扩展，这里需要一个next数组：

int next[4][2] = {  // 顺时针方向 
    {0,1};  // 向右走 
    {1,0};  // 向下走 
    {0,-1};  // 向左走 
    {-1,0};  // 向上走 
}

完整代码如下：

#include<stdio.h>
struct note{
    int x;  // 横坐标
    int y;  // 纵坐标
    int f;  // 父亲在队列中的编号（本题不需要输出路径，可以不需要f） 
    int s;  // 步数 
};
int main()
{
    struct note que[2501];  // 因为地图大小不超过50*50，因此队列扩展不会超过2500个
    
    int a[51][51] = {0};    // 用来存储地图 
    int book[51][51] = {0}; // 数组book的作用是记录哪些点已经在队列中了，防止一个点被重复扩展，并全部初始化为0
    // 定义一个用于表示走的方向的数组
    int next[4][2] = {  // 顺时针方向 
    {0,1},  // 向右走 
    {1,0},  // 向下走 
    {0,-1}, // 向左走 
    {-1,0}, // 向上走 
    };

    int head,tail;
    int i,j,k,n,m,startx,starty,p,q,tx,ty,flag;
 	printf("输入迷宫行、列（直接输入，如5 4）：");
    scanf("%d %d",&n,&m);  // 读入n和m，n为行，m为列
    // 读入迷宫
	printf("输入迷宫（0表示空地，1表示障碍物）和起点、终点坐标(可一起复制)：\n");   
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    scanf("%d %d %d %d",&startx,&starty,&p,&q);
    
    // 队列初始化
    head = 1;
    tail = 1;
    // 往队列插入迷宫入口坐标 
    que[tail].x = startx;
    que[tail].y = starty;
    que[tail].f = 0;
    que[tail].s = 0;
    tail++;
    book[startx][starty] = 1;
    
    flag = 0;  // 用来标记是否到达目标点，0表示暂时没有到达，1表示已到达
    while(head < tail){   // 当队列不为空时循环 
        for(k=0;k<=3;k++) // 枚举四个方向 
        {
            // 计算下一个点的坐标 
            tx = que[head].x + next[k][0];
            ty = que[head].y + next[k][1];
            if(tx < 1 || tx > n || ty < 1 || ty > m) // 判断是否越界 
                continue;
            if(a[tx][ty] == 0 && book[tx][ty] == 0)  // 判断是否是障碍物或者已经在路径中 
            {
                book[tx][ty] = 1;  // 把这个点标记为已经走过。注意bfs每个点通常情况下只入队一次，和深搜不同，不需要将book数组还原
                // 插入新的点到队列中
                que[tail].x = tx;
                que[tail].y = ty;
                que[tail].f = head; // 因为这个点是从head扩展出来的，所以它的父亲是head，本题不需要求路径，因此可省略 
                que[tail].s = que[head].s+1;  // 步数是父亲的步数+1
                tail++; 
                
            }
            if(tx == p && ty == q)  // 如果到目标点了，停止扩展，任务结束，退出循环 
            {
                flag = 1;           // 重要！两句不要写反 
                break;
            }
        }
        if(flag == 1)
            break;
        head++;  // 当一个点扩展结束后，才能对后面的点再进行扩展 
    }    
    printf("%d\n",que[tail-1].s);  // 打印队列中末尾最后一个点，也就是目标点的步数 
     // 注意tail是指向队列队尾（最后一位）的下一个位置，所以这里需要减1 
    getchar();getchar();
    return 0;         
}
/* input
5 4
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
1 1 4 3
*/
/* output
7
*/

运行效果：

第一行有两个数n m，n表示迷宫的行数，m表示迷宫的列数。

接下来n行m列为迷宫，0表示空地，1表示障碍物。

最后一行四个数，前两个数表示迷宫入口的x和y坐标，后两个为小哈的x和y坐标。

1959年，Edward F. Moore率先在“如何从迷宫中寻找出路”这一问题中提出了广度优先搜索算法。1961年，C.Y.Lee在“电路板布线”这一问题中也独立提出了相同的算法。

ref：啊哈磊 《啊哈算法》

-End-