首页 > 代码库 > 搜索 [HDU 1254] 推箱子
搜索 [HDU 1254] 推箱子
推箱子
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5343 Accepted Submission(s): 1503
Problem Description
推箱子是一个很经典的游戏.今天我们来玩一个简单版本.在一个M*N的房间里有一个箱子和一个搬运工,搬运工的工作就是把箱子推到指定的位置,注意,搬运工只能推箱子而不能拉箱子,因此如果箱子被推到一个角上(如图2)那么箱子就不能再被移动了,如果箱子被推到一面墙上,那么箱子只能沿着墙移动.
现在给定房间的结构,箱子的位置,搬运工的位置和箱子要被推去的位置,请你计算出搬运工至少要推动箱子多少格.
现在给定房间的结构,箱子的位置,搬运工的位置和箱子要被推去的位置,请你计算出搬运工至少要推动箱子多少格.
Input
输入数据的第一行是一个整数T(1<=T<=20),代表测试数据的数量.然后是T组测试数据,每组测试数据的第一行是两个正整数M,N(2<=M,N<=7),代表房间的大小,然后是一个M行N列的矩阵,代表房间的布局,其中0代表空的地板,1代表墙,2代表箱子的起始位置,3代表箱子要被推去的位置,4代表搬运工的起始位置.
Output
对于每组测试数据,输出搬运工最少需要推动箱子多少格才能帮箱子推到指定位置,如果不能推到指定位置则输出-1.
Sample Input
15 50 3 0 0 01 0 1 4 00 0 1 0 01 0 2 0 00 0 0 0 0
Sample Output
4
搜索水题、
百度了下，目测网上基本都是搜索套搜索。。。。。
代码可能会有错、没怎么检查就水过了。
应该容易懂、不注释了 - -
#include<iostream>#include<cstdio>#include<queue>#include<cstring>using namespace std;#define INF 0x7ffffff#define N 8struct node{ int px,py; int bx,by; int step;};int ans;int flag;int n,m;int px,py;int bx,by;int mpt[N][N];int vis1[N][N];int vis2[N][N][N][N];int dir[4][2]={0,-1,0,1,-1,0,1,0};bool judge(int x,int y){ if(x>=1 && x<=n && y>=1 && y<=m && mpt[x][y]!=1) return 1; return 0;}void bfs(){ queue<node> q; node now,next; now.bx=bx; now.by=by; now.px=px; now.py=py; now.step=0; vis2[now.bx][now.by][now.px][now.py]=1; q.push(now); while(!q.empty()) { now=q.front(); q.pop(); if(mpt[now.bx][now.by]==3) { ans=min(ans,now.step); return; } for(int i=0;i<4;i++) { next=now; next.px+=dir[i][0]; next.py+=dir[i][1]; if(!judge(next.px,next.py)) continue; if(next.bx==next.px && next.by==next.py) { next.step++; next.bx+=dir[i][0]; next.by+=dir[i][1]; if(!judge(next.bx,next.by)) continue; } if(!vis2[next.bx][next.by][next.px][next.py]) { vis2[next.bx][next.by][next.px][next.py]=1; q.push(next); } } }}void dfs(int x,int y){ if(mpt[x][y]==4) { flag=1; return; } if(flag) return; for(int i=0;i<4;i++) { int tx=x+dir[i][0]; int ty=y+dir[i][1]; if(judge(tx,ty) && mpt[tx][ty]!=2 && !vis1[tx][ty]) { vis1[tx][ty]=1; dfs(tx,ty); vis1[tx][ty]=0; } }}int main(){ int T,i,j; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { scanf("%d",&mpt[i][j]); if(mpt[i][j]==2) { bx=i; by=j; } } } ans=INF; for(i=0;i<4;i++) { px=bx+dir[i][0]; py=by+dir[i][1]; if(judge(px,py)) { flag=0; memset(vis1,0,sizeof(vis1)); dfs(px,py); if(flag) { memset(vis2,0,sizeof(vis2)); bfs(); } } } if(ans==INF) cout<<-1<<endl; else cout<<ans<<endl; } return 0;}
搜索 [HDU 1254] 推箱子
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。