- 对于上一个迷宫的问题也可使用广度优先搜索（Breadth First Search，BFS），也称作宽度优先搜索。
- 深度优先搜索的方法是一直搜索下去，直到走不通，再回到原地。而广度优先搜索是是“一层一层”的扩展进行搜索。最开始假设还是（1，1）处，一步可以到达的点有（1，2）和（2，1）
- 但是还没有找到目标，继续通过这两个（1，2）、（2，1）点往下走。之后，他能走到哪个点呢？（2，2），通过（2，1）还可以到（3，1），并且都是用2步，这里依然需要使用数组进行标记这个点是否走过。
- 然后依次类推继续搜索；
- 在上面的过程中，需要使用个结构体实现队列，
struct note{
int x;
int y;
int s;//记录步数
}
- 从（1，1）开始，先尝试往右走到了（1，2），对其进行判断是否越界或为障碍物或已经走过（使用前边介绍的book数组标记）。
-从（1，1）也可以到达（2，1）。
- 出队时使用head++就可以啦！；
- 代码：
#include<iostream>
using namespace std;
int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
struct note{
int x;
int y;
int f;
int s;
};
int main(){
struct note que[2501];
int head,tail;
int sx,sy,tx,ty,q,p,m,n,flag;
int a[51][51]={0};
int book[51][51]={0};
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
cin>>sx>>sy>>p>>q;
head=1;
tail=1;
que[tail].x=1;
que[tail].y=1;
que[tail].s=0;
tail++;
book[sx][sy]=1;
flag=0;
while(head<tail){
for(int k=0;k<=3;k++){
tx=que[head].x+next[k][0];
ty=que[head].y+next[k][1];
if(tx<1||ty<1||tx>n||ty>m)
continue;
if(a[tx][ty]==0&&book[tx][ty]==0){
book[tx][ty]=1;
que[tail].x=tx;
que[tail].y=ty;
que[tail].f=head;
que[tail].s=que[head].s+1;
tail++;
}
if(tx==p&&ty==q){
flag=1;
break;
}
}
if(flag)
break;
head++;
}
cout<<que[tail-1].s<<endl;
return 0;
}
测试数据：
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
