推箱子（HDOJ 1254）
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
My Code
#include
#include
#include
using namespace std;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int map[10][10];
int v[10][10][10][10];
int n, m, t;
struct node
{
int x, y, bx, by; //x和y是人的位置，bx和by是箱子的位置
int step; //step是箱子移动的步数
friend bool operator<(node a, node b)
{
return a.step > b.step;
}
} s;
bool check(node p)
{
if (p.x < 0 || p.y < 0)
return false;
if (p.x >= n || p.y >= m)
return false;
if (map[p.x][p.y] == 1)
return false;
return true;
}
void bfs()
{
memset(v, 0, sizeof(v));
priority_queue q;
node p, next;
v[s.x][s.y][s.bx][s.by] = 1;
s.step = 0;
q.push(s);
while (!q.empty())
{
p = q.top();
q.pop();
for (int i = 0; i < 4; i++)
{
next.x = p.x + dx[i];
next.y = p.y + dy[i];
if (check(next))
{
next.bx = p.bx;
next.by = p.by;
next.step = p.step;
if (next.x == next.bx && next.y == next.by) //如果人下一步走在了箱子的位置上
{ //那就是在推箱子
int tbx = next.bx + dx[i]; //箱子向人走的方向移动一格
int tby = next.by + dy[i];
if (tbx >= 0 && tbx < n && tby >= 0 && tby < m && map[tbx][tby] != 1)
{ //判断箱子能否移动
next.bx = tbx;
next.by = tby;
next.step++;
}
}
if (map[next.bx][next.by] == 3)
{
cout << next.step << endl;
return;
}
if (!v[next.x][next.y][next.bx][next.by]) //标记重复状态
{
v[next.x][next.y][next.bx][next.by] = 1;
q.push(next);
}
}
}
}
cout << -1 << endl;
}
int main()
{
cin >> t;
while (t--)
{
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
cin >> map[i][j];
if (map[i][j] == 4)
{
s.x = i;
s.y = j;
}
else if (map[i][j] == 2)
{
s.bx = i;
s.by = j;
}
}
bfs();
}
return 0;
} 
OωO
