本文主要是介绍hdu1254（嵌套bfs，两次bfs），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
/*第一次做这种题感觉很有压力，思路还是有点混乱，总是wa，改了好多次才ac的
思路：把箱子的移动当做第一层bfs，队列节点要用到当前箱子坐标（x，y），走的次数step，当前人的weizhi（man_x，man_y），要判断人能否将箱子推到某点时要嵌套第二层bfs（人的移动）；
代码如下： */
#include<iostream>
#include<algorithm>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<time.h>
#include<math.h>#define eps 1e-9
#define N 10
#define P system("pause")
using namespace std;
int n,m;
int a[N][N];
int man_sx,man_sy,box_sx,box_sy;
int man_ex,man_ey,box_ex,box_ey;
int d[4][2]={{-1,0},{1,0},{0,-1},{0,1}};struct node
{int x,y;int man_x,man_y;int step;
};bool judge(int x,int y)
{if(a[x][y]!=1 && x>=0 && x<n && y>=0 && y<m) return 1;return 0;
}
bool bfs_man(int x,int y)//x,y是箱子的位置
{int vis[N][N]={0};queue<node> q;node u,v;u.x=man_sx;u.y=man_sy;q.push(u);vis[man_sx][man_sy]=1;while(!q.empty()){u=q.front();q.pop();if( u.x == man_ex && u.y == man_ey ) return 1; for(int i=0;i<4;i++){int nx=u.x+d[i][0];int ny=u.y+d[i][1];if(judge(nx,ny) && !vis[nx][ny] && (nx!=x||ny!=y) ) //注意不要忘记判断是否撞倒箱子********************** {v.x=nx;v.y=ny;q.push(v);vis[nx][ny]=1; } }}return 0;
}int bfs_box()
{int vis[N][N][4]={0}; //箱子到达同一点，人所在的位置可能有四种 queue<node> q;node u,v;u.x=box_sx;u.y=box_sy;u.step=0;u.man_x=man_sx;u.man_y=man_sy;q.push(u);///vis[box_sx][box_sy][]=1;while(!q.empty()){u=q.front();q.pop();if(u.x==box_ex && u.y==box_ey) return u.step;for(int i=0;i<4;i++){int nx=u.x+d[i][0];int ny=u.y+d[i][1];if(judge(nx,ny)&&!vis[nx][ny][i]){man_sx=u.man_x; //时刻更新人的当前位置和目标位置，以确保bfs_man的正确性 man_sy=u.man_y; man_ex=u.x-d[i][0]; man_ey=u.y-d[i][1]; if(judge(man_ex,man_ey)&&bfs_man(u.x,u.y)) //判断人的目标位置是否越界，和能否到达目标位置{v.man_x=u.x;v.man_y=u.y; //更新人的当前位置v.x=nx;v.y=ny;v.step=u.step+1;q.push(v);vis[nx][ny][i]=1; } } }}return -1;
}int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);ccint t;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);int i,j;for(i=0;i<n;i++) for(j=0;j<m;j++){scanf("%d",&a[i][j]);if(a[i][j]==2){box_sx=i;box_sy=j;}else if(a[i][j]==3){box_ex=i;box_ey=j;}else if(a[i][j]==4){man_sx=i;man_sy=j;}}int z=bfs_box();printf("%d\n",z);} //P; return 0;
}这篇关于hdu1254（嵌套bfs，两次bfs）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
