No.4.3 层层递进-广度优先搜索
一、深度优先搜索：从开始位置进行尝试，直到走不通的时候，再返回到上一层“递归“继续尝试
广度优先搜索：从开始位置起，搜索每一种可能路径并加入到队列，再从队列中的所有元素搜索所有的下一层可能路径，即首先穷尽最上层可能，再逐层递进，那么找到目标的那一刻，最短层数既是最短路径！
把此图顺时针旋转45度，呈现树的形态，即可以更加形象化的视线，理解广度优先搜索算法！
#include
struct node{
int x; //横坐标
int y; //纵坐标
int s; //步数
};
//算法是用了两种数据结构实现的：二维数组和队列（队列元素是一个三维数组）
int main(){
struct node que[2501]; //这是一个队列，队列中的元素是 struct node
int a[51][51]={0},book[51][51]={0}; //二维平面依旧使用二维数组表示
int next[4][2]={
{0,1}, // 右
{1,0}, // 下
{0,-1}, // 左
{-1,0} // 上
};
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);
//队列初始化
int head=1,tail=1;
que[tail].x=startx;
que[tail].y=starty;
que[tail].s=0;
tail++; //tail指向空值，所以步数的增加应该是 que[head].s+1，下一步尝试也是操作que[head]
book[startx][starty]=1;
flag=0;
while(head
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; //宽搜的点不能取消标记，否则下一层的点向上搜索时，会产生无限循环！
que[tail].x=tx;
que[tail].y=ty;
que[tail].s=que[head].s+1;
tail++;
}
if(tx==p && ty==q){ //只要找到(p,q)，就一定是最短路径，退出循环
flag=1;
break;
}
}
if(flag==1) //只要找到(p,q)，就一定是最短路径，退出程序
break;
head++; //同一级队列元素尝试完毕，即可退出队列，无需取消标记book
}
printf("%d",que[tail-1].s);
getchar();getchar();return 0;
}
二、将上面的例子增加点难度，要求打印出最短路径（并不要求打印出所有的最短路径）：用一个笨方法，保存当前节点的父节点
struct node{
int x; //横坐标
int y; //纵坐标
int s; //步数
int f[3]; //保存父节点的x,y,s
};
//算法是用了两种数据结构实现的：二维数组和队列（队列元素是一个三维数组）
int main(){
struct node que[2501]; //这是一个队列，队列中的元素是 struct node
int a[51][51]={0},book[51][51]={0}; //二维平面依旧使用二维数组表示
int next[4][2]={
{0,1}, // 右
{1,0}, // 下
{0,-1}, // 左
{-1,0} // 上
};
int i,j,k,n,m,startx,starty,p,q,tx,ty,flag;
int cu,pa;
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);
int head=1,tail=1;
que[tail].x=startx;
que[tail].y=starty;
que[tail].s=0;
que[tail].f[0]=startx;
que[tail].f[1]=starty;
que[tail].f[2]=que[tail].s;
tail++; //tail指向空值
book[startx][starty]=1;
flag=0;
while(head
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;
que[tail].x=tx;
que[tail].y=ty;
que[tail].s=que[head].s+1;
que[tail].f[0]=que[head].x;
que[tail].f[1]=que[head].y;
que[tail].f[2]=que[head].s;
tail++;
}
if(tx==p && ty==q){
flag=1;
//打印所有路径，用作验证
for (cu=tail-1;cu>0;cu--)
printf("z=%d, %d %d %d, %d %d %d\n",cu,que[cu].x,que[cu].y,que[cu].s,que[cu].f[0],que[cu].f[1],que[cu].f[2]);
//打印最短路径
cu = tail-1;
while(cu>1){
pa=cu-1;
while(true){
if(que[cu].f[0]==que[pa].x && que[cu].f[1]==que[pa].y && que[cu].f[2]==que[pa].s){
printf("cur=%d %d %d, pre=%d %d %d\n",que[cu].x,que[cu].y,que[cu].s,que[pa].x,que[pa].y,que[pa].s);
break;
}
else
pa--;
}
cu=pa;
}
break;
}
}
if(flag==1)
break;
head++;
}
printf("\n最小路径长度为%d",que[tail-1].s);
getchar();getchar();return 0;
}
三、方法二太麻烦了，优雅点
struct node{
int x; //横坐标
int y; //纵坐标
int s; //步数
int f; //保存父节点的指针（head）
};
int main(){
struct node que[2501]; //这是一个队列，队列中的元素是 struct node
int a[51][51]={0},book[51][51]={0}; //二维平面依旧使用二维数组表示
int next[4][2]={
{0,1}, // 右
{1,0}, // 下
{0,-1}, // 左
{-1,0} // 上
};
int i,j,k,n,m,startx,starty,p,q,tx,ty,flag;
int cu,pa;
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);
int head=1;tail=1;
que[tail].x=startx;
que[tail].y=starty;
que[tail].s=0;
que[tail].f=0;
tail++; //tail指向空值
book[startx][starty]=1;
flag=0; //每一个head，尝试完所有可能之后，就会被释放，并标记为book[tx][ty]=1，防止后续被重新入栈 //打印已经探索出来的路径，用作验证 cu=tail-1; 四、如果还想求解共有多少条最短路径的话，广度优先搜索就不合适了，因为这里为了不陷入循环，就像一条有向图一样，不准走回头路，那么就不能对同一个节点进行多种尝试！ 这时，还是要用上节中的深度优先算法，或者排列组合算法！
while(head
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;
que[tail].x=tx;
que[tail].y=ty;
que[tail].s=que[head].s+1;
que[tail].f=head; //当前尝试的父节点都是head指针所指向的对象
tail++;
}
if(tx==p && ty==q){
flag=1;
for (cu=tail-1;cu>0;cu--)
printf("z=%d, %d %d %d, %d\n",cu,que[cu].x,que[cu].y,que[cu].s,que[cu].f);
while(cu>0){ //看这里，知道为何初始化的时候“que[tail].f=0”了吧！
printf("z=%d, %d %d %d, %d\n",cu,que[cu].x,que[cu].y,que[cu].s,que[cu].f);
cu=que[cu].f; //倒序递归
}
break;
}
}
if(flag==1) //已经找到了最短路径，结束程序，虽然还有其他可能的最短路径！
break;
head++;
}
printf("\n最小路径长度为%d",que[tail-1].s);
getchar();getchar();return 0;
}