首页 > 代码库 > hdu1254（bfs+dfs）
hdu1254（bfs+dfs）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1254
分析：
真正移动的是箱子，但是要移动箱子需要满足几个条件。
1.移动方向上没有障碍。
2.箱子后方没有障碍。
3.人可以到达箱子后方的地方。这里dfs或bfs都可以实现
按条件搜索即可。
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 100010using namespace std;typedef struct node{ int Bx,By; int Mx,My; int step; bool operator<(const node &a)const { return step>a.step; }}node;int dx[]={0,0,1,-1};int dy[]={1,-1,0,0};int hash[10][10][10][10];int vis[10][10],s[10][10];int Bx,By,Mx,My,Nx,Ny;int found,n,m;node make_node(int a,int b,int x,int y){ node temp; temp.Bx=a;temp.By=b; temp.Mx=x;temp.My=y; temp.step=0; return temp;}int judge(int x,int y){ return x>=0&&x<n&&y>=0&&y<m&&s[x][y]!=1;}void dfs(int Nx,int Ny,int Mx,int My){ if(Nx==Mx&&Ny==My) { found=1;return; } for(int i=0;i<4&&!found;i++) { int x=Nx+dx[i]; int y=Ny+dy[i]; if(judge(x,y)&&!vis[x][y]) vis[x][y]=1,dfs(x,y,Mx,My); }}void bfs(int Bx,int By,int Mx,int My){ priority_queue<node>que; node p,q; p=make_node(Bx,By,Mx,My); que.push(p); while(!que.empty()) { node p=que.top();que.pop(); if(s[p.Bx][p.By]==3) { printf("%d\n",p.step);return; } for(int i=0;i<4;i++) { q=p; q.Bx=p.Bx+dx[i];//箱子移动的地方 q.By=p.By+dy[i]; Nx=p.Bx-dx[i];//箱子的后方 Ny=p.By-dy[i]; if(judge(q.Bx,q.By)&&judge(Nx,Ny)&&!hash[q.Bx][q.By][Nx][Ny]) { memset(vis,0,sizeof(vis)); vis[p.Bx][p.By]=vis[Nx][Ny]=1;//注意这里箱子将成为阻碍物 found=0; dfs(Nx,Ny,p.Mx,p.My);//判断人是否可达箱子后面 if(found) { hash[q.Bx][q.By][Nx][Ny]=1; q.Mx=p.Bx;q.My=p.By;q.step++; que.push(q); } } } } printf("-1\n"); return;}void init(){ memset(hash,0,sizeof(hash)); memset(s,0,sizeof(s)); for(int i=0;i<n;i++) for(int j=0;j<m;j++) { scanf("%d",&s[i][j]); if(s[i][j]==2) { Bx=i;By=j; } if(s[i][j]==4) { Mx=i;My=j; } }}int main(){ int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); init(); bfs(Bx,By,Mx,My); }}
hdu1254（bfs+dfs）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。