推箱子

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

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 解题思路：首先想到的肯定是bfs+优先队列，每个节点记录的是箱子的位置，以及推动箱子的次数和箱子移动的方向，每次推箱子之前，箱子有四个方向选择，每个方向能否推动主要是看人是否可以到箱子的背后去推它。这里可以用dfs去搜索。 #include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std;struct Node {int x,y;int cnt,d; //d表示当前移动的位置Node(){}Node(int _x,int _y,int _cnt,int _d){x = _x, y = _y;cnt = _cnt, d = _d;}friend bool operator < (const Node &a,const Node &b){return a.cnt > b.cnt;} }; int n,m,map[10][10]; int sx,sy,ex,ey; int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; bool vis[10][10][4],reach[10][10];void dfs(int x,int y,int tx,int ty) //(tx,ty)表示此时箱子的位置 {reach[x][y] = true;for(int i = 0; i < 4; i++){int newx = x + dir[i][0];int newy = y + dir[i][1];if(newx == tx && newy == ty) continue;if(newx < 1 || newx > n || newy < 1 || newy > m) continue;if(map[newx][newy] == 1 || reach[newx][newy] == true) continue;dfs(newx,newy,tx,ty);} }int bfs(int tx,int ty) //(tx,ty)表示初始时，箱子的位置 {priority_queue<Node> que;memset(vis,false,sizeof(vis));memset(reach,false,sizeof(reach));Node cur,next;dfs(sx,sy,tx,ty);if(reach[tx+1][ty] == true)que.push(Node(tx,ty,0,0));if(reach[tx-1][ty] == true)que.push(Node(tx,ty,0,1));if(reach[tx][ty+1] == true)que.push(Node(tx,ty,0,2));if(reach[tx][ty-1] == true)que.push(Node(tx,ty,0,3));while(!que.empty()){cur = que.top();que.pop();if(cur.x == ex && cur.y == ey) return cur.cnt;vis[cur.x][cur.y][cur.d] = true;memset(reach,false,sizeof(reach));if(cur.d == 0)dfs(cur.x+1,cur.y,cur.x,cur.y);else if(cur.d == 1)dfs(cur.x-1,cur.y,cur.x,cur.y);else if(cur.d == 2)dfs(cur.x,cur.y+1,cur.x,cur.y);else if(cur.d == 3)dfs(cur.x,cur.y-1,cur.x,cur.y);for(int i = 0; i < 4; i++){int newx = cur.x + dir[i][0];int newy = cur.y + dir[i][1];if(newx < 1 || newx > n || newy < 1 || newy > m) continue;if(map[newx][newy] == 1 || vis[newx][newy][i] == true) continue;next.x = newx, next.y = newy, next.cnt = cur.cnt+1, next.d = i;if(i == 0 && reach[cur.x+1][cur.y])que.push(next);else if(i == 1 && reach[cur.x-1][cur.y])que.push(next);else if(i == 2 && reach[cur.x][cur.y+1])que.push(next);else if(i == 3 && reach[cur.x][cur.y-1])que.push(next);}}return -1; }int main() {int t,tx,ty;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++){scanf("%d",&map[i][j]);if(map[i][j] == 4)sx = i, sy = j;else if(map[i][j] == 3)ex = i, ey = j;else if(map[i][j] == 2)tx = i, ty = j;}printf("%d\n",bfs(tx,ty));}return 0; }

与50位技术专家面对面20年技术见证，附赠技术全景图

总结

以上是生活随笔为你收集整理的hdu 1254（dfs+bfs+优先队列）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。