[编程题] 推箱子
大家一定玩过“推箱子”这个经典的游戏。具体规则就是在一个N*M的地图上，有1个玩家、1个箱子、1个目的地以及若干障碍，其余是空地。玩家可以往上下左右4个方向移动，但是不能移动出地图或者移动到障碍里去。如果往这个方向移动推到了箱子，箱子也会按这个方向移动一格，当然，箱子也不能被推出地图或推到障碍里。当箱子被推到目的地以后，游戏目标达成。现在告诉你游戏开始是初始的地图布局，请你求出玩家最少需要移动多少步才能够将游戏目标达成。
输入描述:
每个测试输入包含1个测试用例
第一行输入两个数字N，M表示地图的大小。其中0<N，M<=8。
接下来有N行，每行包含M个字符表示该行地图。其中 . 表示空地、X表示玩家、*表示箱子、#表示障碍、@表示目的地。
每个地图必定包含1个玩家、1个箱子、1个目的地。
输出描述:
输出一个数字表示玩家最少需要移动多少步才能将游戏目标达成。当无论如何达成不了的时候，输出-1。
输入例子:
4 4
....
..*@
....
.X..
6 6
...#..
......
#*##..
..##.#
..X...
.@#...
输出例子:
3 11
题解：因为n,m较小，开四维数组搜下即可。
#include <bits/stdc++.h> using namespace std; const int N=10; int dir[4][2]={{-1,0},{0,1},{0,-1},{1,0}}; char c[N][N]; int vis[N][N][N][N]; int n,m,x,y,bx,by,ex,ey; bool check(int x,int y,int bx,int by) { if(x<0||x>=n||y<0||y>=m||c[x][y]=='#') return 1; if(bx<0||bx>=n||by<0||by>=m||c[bx][by]=='#') return 1; if(vis[x][y][bx][by]) return 1; return 0; } struct edge{ int x,y,bx,by,step; edge(int x,int y,int bx,int by,int step) :x(x),y(y),bx(bx),by(by),step(step){} friend bool operator < (edge x,edge y) { return x.step>y.step; } }; void bfs() { memset(vis,0,sizeof(vis)); priority_queue<edge> q; edge c(x,y,bx,by,0); q.push(c); vis[x][y][bx][by]=1; while(!q.empty()){ c=q.top();q.pop(); if(c.bx==ex&&c.by==ey){ printf("%d ",c.step); return ; } for(int i=0;i<4;i++) { int x=c.x+dir[i][0],y=c.y+dir[i][1]; if(check(x,y,c.bx,c.by)) continue; ////这里不能先标记 因为推箱子可能从四个方向推过来的 if(x==c.bx&&y==c.by){//碰到箱子 int tx=c.bx+dir[i][0]; int ty=c.by+dir[i][1]; if(check(x,y,tx,ty)) continue; vis[x][y][tx][ty]=1; edge ne(x,y,tx,ty,c.step+1); q.push(ne); } else{//没碰到箱子 vis[x][y][c.bx][c.by]=1; edge ne(x,y,c.bx,c.by,c.step+1); q.push(ne); } } } puts("-1"); return ; } int main() { while(scanf("%d%d",&n,&m)!=EOF){ for(int i=0;i<n;i++) scanf("%s",c[i]); for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(c[i][j]=='X') x=i,y=j; else if(c[i][j]=='*') bx=i,by=j; else if(c[i][j]=='@') ex=i,ey=j; bfs(); } return 0; }