解救小哈——广度优先搜索

题目描述：

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

迷宫由m行n列的单元格组成的（m和n都小于50），每个单元格要么是空地要么是障碍物，你的任务是帮小哼找到一条从迷宫的起点通往小哈所在位置的最短路径。

样例输入：

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

题解：

#include<stdio.h>
struct note {
    int x; //横坐标
    int y; //纵坐标
    int s; //步数
};

int main(){
    struct note que[2501]; //因为地图大小不超过50*50，因此队列拓展不会 超过2500个

    int a[51][51] = {0}, book[51][51] = {0};

    //定义一个用于表示走的方向的数组
    int next[4][2] = {{0, 1},{1, 0},{0, -1},{-1, 0}};

    int head, tail;
    int i, j, k, n, m, startx, starty, tx, ty, flag, p, q;

    scanf("%d %d",&n, &m);
    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].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数 组还原
                book[tx][ty] = 1;
                //插入新的点到队列
                que[tail].x = tx;
                que[tail].y = ty;

                que[tail].s = que[head].s + 1; //步数是父亲的步数 + 1
                tail++;
            }
            //如果找到目标点了，就停止扩展，任务结束，退出循环
            if (tx == p && ty == q){
                flag = 1;
                break;
            }
        }
        if (flag == 1){
            break;
        }
        head ++; //当一个扩展结束后，head++才能对后面的点再进行扩展
    }
    //打印队列中末尾最后一个点（目标点）的步数
    //注意tail是指向队列队尾（即最后一位）的下一个位置，所以这需要-1
    printf("%d\n",que[tail-1].s);

    return 0;
}