HDU 1254 推箱子 C++优先队列+bfs

本文主要是介绍HDU 1254 推箱子 C++优先队列+bfs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1254
推箱子是一个很经典的游戏.今天我们来玩一个简单版本.在一个M*N的房间里有一个箱子和一个搬运工,搬运工的工作就是把箱子推到指定的位置,注意,搬运工只能推箱子而不能拉箱子,因此如果箱子被推到一个角上(如图2)那么箱子就不能再被移动了,如果箱子被推到一面墙上,那么箱子只能沿着墙移动.

现在给定房间的结构,箱子的位置,搬运工的位置和箱子要被推去的位置,请你计算出搬运工至少要推动箱子多少格.

输入格式
输入数据的第一行是一个整数T(1<=T<=20),代表测试数据的数量.
然后是T组测试数据,每组测试数据的第一行是两个正整数M,N(2<=M,N<=7),代表房间的大小.
然后是一个M行N列的矩阵,代表房间的布局,其中0代表空的地板,1代表墙,2代表箱子的起始位置,3代表箱子要被推去的位置,4代表搬运工的起始位置.
输出格式
对于每组测试数据,输出搬运工最少需要推动箱子多少格才能帮箱子推到指定位置,如果不能推到指定位置则输出-1.

样例输入
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

样例输出
4

思路

求最短时间一般用的是bfs。但这道题用普通的bfs会WA，因为要求的最短路是推动箱子的最小步数，而普通的bfs是搬运工移动的最小次数，而移动的次数少不一定能代表推动箱子次数少，例如下面这组数据：
1
3 5
1 1 4 0 0
0 2 0 0 0
0 3 0 0 0
若用普通的bfs运行这组数据，得到的结果是5，而用优先队列+bfs运行结果是3，因为此时推动箱子次数少，但搬运工走的步数要多（若想要只推动3次箱子则必须绕几个弯才能达到终点）。故普通的bfs会WA。

注意事项

虽然优先队列可以用C++的STL模板库里的priority_queue，如下：

priority_queue<node> w; //这是元素大的排前面，若想要元素小的排前面则要用priority_queue<node,vector<int>,greater<int> > w;

但是需要重载一个<，并注意在前面加上friend，如下：

friend inline bool operator < (node a,node b) {return a.t>b.t;   //注意符号不要写反，是大于号
}

每次bfs完都要把队列里剩下的元素全部弹出，如下：

while(!w.empty())   w.pop();

bfs函数

首先要用一个数组来记录状态。这里由于人和箱子的位置都要记录，所以应用一个四维数组来记录（其实由于n和m不超过7，二维数组，十位表示横坐标，个位表示纵坐标也是可以的）。
当人碰到箱子的时候箱子就向同样的方向移动一次。
其他和普通的bfs是一样的，就不详细说了。
搜完所有状态后若仍无解则返回-1。

代码

#include<stdio.h>
#include<cstring>
#include<queue>
using namespace std;
const int Size=13;
const int dx[] = {1,0,0,-1};
const int dy[] = {0,1,-1,0};
int map[Size][Size];
bool memory[Size][Size][Size][Size];    //判重数组
int m,n,x1,y1,x2,y2,x3,y3;
struct node {       //节点int x,y;int bx,by;int t;friend inline bool operator < (node a,node b) {return a.t>b.t;}
};
priority_queue<node>w;
void push_queue(int x,int y,int bx,int by,int time) {node a;a.x=x,a.y=y,a.bx=bx,a.by=by,a.t=time;w.push(a);memory[x][y][bx][by]=true;
}
int read() {            //快速读入函数int x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-')    f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=10*x+ch-'0';ch=getchar();}return x*f;
}
void init() {           //初始化memset(memory,0,sizeof(memory));m=read(),n=read();for(int i=1; i<=m; i++) {for(int j=1; j<=n; j++) {map[i][j]=read();switch(map[i][j]) {case 2: x3=i;y3=j;break;case 3: x2=i;y2=j;break;case 4: x1=i;y1=j;break;default:break;}}}while(!w.empty())   w.pop();    //将队列里剩下的元素弹出队列push_queue(x1,y1,x3,y3,0); 
}
inline bool judge(int x,int y) {    //判断(x,y)满不满足入队要求return (x>=1 && y>=1 && x<=m && y<=n && map[x][y]!=1);
}
int bfs() {node now,nxt;int nx,ny,bx,by,nt;while(!w.empty()) {now=w.top();w.pop();if(map[now.bx][now.by]==3)  return now.t;for(int i=0; i<4; i++) {nx=now.x+dx[i],ny=now.y+dy[i];bx=now.bx,by=now.by;nt=now.t;if(judge(nx,ny) && (!memory[nx][ny][bx][by])) {if(nx==bx && ny==by) {bx+=dx[i],by+=dy[i],nt++;if(!judge(bx,by)||memory[nx][ny][bx][by])continue;push_queue(nx,ny,bx,by,nt);} else {push_queue(nx,ny,bx,by,nt);}}}}return -1;
}
int main() {int t=read(),out;while(t--) {init();printf("%d\n",bfs());}return 0;
}