3. 广度优先搜索

广度优先搜索(Breadth First Search，BFS)，也称为宽度优先搜索。

还是用一个二维数组来存储上一小节的迷宫。

最开始的时候小哼在迷宫(1，1)处，他可以往右走或者往下走。

在上一节中我们的方法是，先让小哼往右边走，然后一直尝试下去，直到走不通的时候再回到这里。这样是深度优先，可以通过函数的递归实现。

现在介绍另外一种方法：通过“一层一层”扩展的方法来找到小哈。扩展时每发现一个点就将这个点加入到队列中，直至走到小哈的位置(p.q)时为止，具体如下:

最开始小哼在入口(1，1)处，一步之内可以到达的点有(1，2)和(2，1)。

但是小哈并不在这两个点上，那小哼只能通过(1.2)和(2.1)这两点继续往下走。

发现(2，2)这个点既可以从(1，2)到达，也可以从(2，1)到达，并且都只使用了2步。

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

继续往下尝试，现在3步可以到达的点有(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;

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

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

这里还是规定一个顺序，即按照顺时针的方向来尝试(也就是以右、下、左、上的顺序尝试).

发现丛(1，1)还是可以到达(2，1)。因此也需要将(2，1)也加入队列，代码实现与刚才对(1，2)的操作是一样的。

对(1，1)扩展完毕后，其实(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}};

完整代码实现如下：

struct note
{
	int x;//横坐标
	int y;//纵坐标
	int s;//步数
};


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

	int a[51][51] = {0};
	int 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, p, q, ,tx, ty, flag;

	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 = 1;
	que[tail].y = 1;
	que[tail].s = 0;
	tail++;
	book[startx][starty] = 1;

	flag = 0;//用来标记是否到达目标点，0表示暂时还没有到达，1表示到达
	//当队列不为空的时候循环
	while(head < tail) {
		//枚举4个方向
		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);
	getchar();getchar();
	return 0;
}

数据验证：

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

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

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

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

返回值：
7

参考

《啊哈！算法》 —— 第4章 万能的搜索