推箱子

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 8578    Accepted Submission(s): 2499 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 1 5 5 0 3 0 0 0 1 0 1 4 0 0 0 1 0 0 1 0 2 0 0 0 0 0 0 0   Sample Output

4

思路：用三维数组判重，因为方向不一样是不同的状态。推箱子的流程是，首先确定要往那边推，判断能不能推，然后判断人能不能到达推箱子的那个位置。

代码：

//思路：用三维数组判重，因为方向不一样是不同的状态。推箱子的流程是，首先确定要往那边推，判断能不能推，然后判断人能不能到达推箱子的那个位置。 #include<stdio.h> #include<string.h> #include<stdlib.h> #include<queue> using namespace std; struct node { int x,y; int step; int rx,ry; }; struct node1 { int x, y; }; int map[10][10]; int vis[10][10][10]; int vis1[10][10]; int n,m,xsx,ysy,zx,zy,rx,ry; int d[4][2]={1,0,-1,0,0,1,0,-1}; int ans; int jude(int x,int y) { if(x>=1&&x<=n&&y>=1&&y<=m) return 1; return 0; } int dfs(int zx,int zy,int ax,int ay,int xx,int yy) { // printf("1 %d %d %d %d\n",xx,yy,ax,ay);; queue<node1>q; node1 a={xx,yy}; q.push(a); vis1[xx][yy]=1; while(!q.empty()) { a=q.front(); q.pop(); if(a.x==zx&&a.y==zy) return 1; for(int i=0;i<4;i++) { int xxx=a.x+d[i][0]; int yyy=a.y+d[i][1]; if(!jude(xxx,yyy)) continue; if(map[xxx][yyy]==1) continue; if(xxx==ax&&yyy==ay) continue; if(vis1[xxx][yyy]) continue; vis1[xxx][yyy]=1; node1 b={xxx,yyy}; q.push(b); } } return 0; } void bfs() { node a={xsx,ysy,0,rx,ry}; queue<node>q; q.push(a); vis[xsx][ysy][0]=1; vis[xsx][ysy][1]=1; vis[xsx][ysy][2]=1; vis[xsx][ysy][3]=1; while(!q.empty()) { a=q.front(); q.pop(); if(a.x==zx&&a.y==zy) { ans=a.step; return ; } // printf("s %d %d\n",a.x,a.y); for(int i=0;i<4;i++) { int xx=a.x+d[i][0]; int yy=a.y+d[i][1]; int renx=a.x; int reny=a.y; int px=a.x-d[i][0]; int py=a.y-d[i][1]; if(!jude(xx,yy)||!jude(px,py)) continue;//判断箱子推动的位置和要推箱子要站的位置是否出界 if(vis[xx][yy][i]) continue; if(map[xx][yy]==1||map[px][py]==1) continue;//判断可不可以走 memset(vis1,0,sizeof(vis1)); if(!dfs(px,py,a.x,a.y,a.rx,a.ry)) continue;//判断能不能到 vis[xx][yy][i]=1; node b={xx,yy,a.step+1,renx,reny}; q.push(b); } } ans=-1; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { for(int k=0;k<4;k++) vis[i][j][k]=0; scanf("%d",&map[i][j]); if(map[i][j]==3) {zx=i,zy=j; map[i][j]=0;}//记录几个关键点的坐标。是的地图只有0&&1； if(map[i][j]==2) {xsx=i,ysy=j;map[i][j]=0;} if(map[i][j]==4) {rx=i,ry=j;map[i][j]=0;} } } //memset(vis,0,sizeof(vis)); bfs(); printf("%d\n",ans); } }