题目描述

一个M*N的迷宫矩阵由 0 和 1 组成，1 表示墙壁，0 表示通路。

一只小老鼠从左上角即坐标（0,0）出发，只能走上下左右四个方向（不能走斜线），问小老鼠能否吃到右下角出口即坐标（M-1,N-1）处的奶酪。

输入格式

第一行输入空格分开的两个整数，表示迷宫的行数和列数。

然后输入 M 行 N 列的迷宫矩阵。保证左上角数字为 0。

数据范围

5 <= M，N <= 50

输出格式

若能走到出口，输出 "yes" ，否则输出 "no"。

样例

5 5
0 0 1 0 1
0 0 1 0 0
0 1 0 1 1
0 1 0 0 0
0 0 0 0 0

yes

5 5
0 0 1 0 1
0 0 1 0 0
0 1 0 1 1
0 1 1 0 0
0 0 1 0 0

no

算法分析

我们不妨把上面的地图做一些标记，我们让每一个格子都赋 1 个名称，用 A/B/C/D.....来标记（幸好只有 25 个格子，所以用 1 个字母就可以标识了）。然后，我们用绿色的格子来表示可以走到格子，用红色格子用来表示障碍格子。得到下图：

1. 出发点是 A，从 A 往外探索，找到了 2 个儿子：B 和 F

2. 上一轮新找到的点是 B 和 F，从 B 和 F 往外探索，各自找到 1 个儿子：G 和 K 。

我们假定找儿子的顺序是 右-下-左-上，所以 G 成了 B 的儿子，然后就不把 G 看作 F 的儿子了（重复计算没有任何好处）。如果改变查找的顺序，会得到略有不同的情况，但是算法的意思不变，最终的计算结果不变。

3. 上一轮新找到的点是 G 和 K，从 G 和 K 往外探索。G 找到了 1 个儿子：P； K 没有儿子。

4. 重复上述的搜索方法，最终搜索结果为：

所以，在第 8 步的时候找到了迷宫的出口 Y 。

如果我们把搜索到的点按照顺序连起来，会是下图这样：

上面这个按层拓展搜索的方法，就是 BFS 算法的思想了。我们可以把构建一个点的队列，不断的把新找到的点放在队列的尾部，不断的从队列的头部把点拿出来，继续搜索，从而把上面的搜索思想转变成程序。

完善程序

#include<bits/stdc++.h>
using namespace std;
int v[2000][2000];
bool Lock[2000][2000]; // Lock 数组记录一个点是否已经被找到过，避免重复搜索
bool Found;
int n,m,head,tail;
struct point // 点的结构体
{
    int x,y;
} q[4000000]; // 点的队列
int diff[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}; // 位置偏移数组
void  bfs()
{
    int xx,yy,k;
    point t;
	while( 填空(1) ) //如果队列还有内容
    {
    	t = 填空(2); //从队列的头部拿出一个点
	    if(t.x==n-1&&t.y==m-1)
	    {
	        填空(3) ; //记录一下，找到了
	        return; // 找到了就不需要再找了。
			// 这个判断放在下方也可以，但是如果 出发点和终点相同，那么就会出问题
	    }
	    for(k=0;k<4;k++)
	    {
	        xx = t.x + 填空(4);
	        yy = t.y + diff[k][1];
	        if(xx<n&&xx>=0&&yy<m&&yy>=0&&Lock[xx][yy]==填空(5)&&v[xx][yy]==填空(6))
	        {
                //把新找到的点放到队列的尾部
	        	q[tail].x = xx;
	            q[tail].y = yy;
				填空(7);
	            Lock[xx][yy] = true;
	        }
	    }
	}

}
int main()
{
    int i,j;
    scanf("%d %d",&n,&m);
    for(i=0;i<n;i++)
        for(j=0;j<m;j++)
			scanf("%d",&v[i][j]);
    
    //把 (0,0) 放入队列
    q[0].x=0;
    q[0].y=0;
    tail = 填空(8);

    Lock[0][0] = true; //标记 （0,0） 已经找到过

    bfs();

    if(Found) printf("yes");
    else printf("no");
    return 0;
}

填空(1):{{ input(1) }}

填空(2):{{ input(2) }}

填空(3):{{ input(3) }}

填空(4):{{ input(4) }}

填空(5):{{ input(5) }}

填空(6):{{ input(6) }}

填空(7):{{ input(7) }}

填空(8):{{ input(8) }}