HDU 1254 推箱子 解题报告

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也可以是BFS，注意，人不能穿过箱子。判重需要开4维数组，分别保存人的坐标和箱子的坐标。预处理起点后可以标记成空的地板，方便操作。

AC代码：

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
int m, n, map[10][10];
bool vis[10][10][10][10];
const int dx[] = {0, 0, 1, -1},
			dy[] = {1, -1, 0, 0};
struct node
{
	int mx, my, bx, by, step;
};
struct pos
{
	int x, y;
};
node start;
queue <node> q;
void input()
{
	scanf("%d%d", &m, &n);
	for (int i = 0; i < m; i++)
		for (int j = 0; j < n; j++)
		{
			scanf("%d", &map[i][j]);
			if (map[i][j] == 2)
			{
				map[i][j] = 0;
				start.bx = i;
				start.by = j;
			}
			else if (map[i][j] == 4)
			{
				map[i][j] = 0;
				start.mx = i;
				start.my = j;
			}
		}
}
void pre()
{
	while (!q.empty())
		q.pop();
	memset(vis, 0, sizeof(vis));
}
bool check(int x, int y)
{
	if (x < 0 || x >= m || y < 0 || y >= n || map[x][y] == 1)
		return 0;
	return 1;
}
bool bfs_man(int sx, int sy, int ex, int ey, int bx, int by)
{
	if (!check(sx, sy))
		return 0;
	queue <pos> qq;
	bool vis2[10][10] = {0};
	vis2[sx][sy] = vis2[bx][by] = 1;
	qq.push((pos){sx, sy});
	while (!qq.empty())
	{
		pos u = qq.front();
		qq.pop();
		if (u.x == ex && u.y == ey)
			return 1;
		pos next;
		for (int i = 0; i < 4; i++)
		{
			next.x = u.x + dx[i];
			next.y = u.y + dy[i];
			if (!check(next.x, next.y) || vis2[next.x][next.y])
				continue;
			vis2[next.x][next.y] = 1;
			qq.push(next);
		}
	}
	return 0;
}
void bfs()
{
    pre();
    q.push(start);
    vis[start.bx][start.by][start.mx][start.my] = 1;
    while (!q.empty())
	{
		node u = q.front();
		q.pop();
		if (map[u.bx][u.by] == 3)
		{
			printf("%d\n", u.step);
			return;
		}
		node next;
		for (int i = 0; i < 4; i++)
		{
			next.bx = u.bx + dx[i];
			next.by = u.by + dy[i];
			next.mx = u.bx;
			next.my = u.by;
			next.step = u.step + 1;
			if (!check(next.bx, next.by) || vis[next.bx][next.by][next.mx][next.my] || !bfs_man(u.mx, u.my, u.bx - dx[i], u.by - dy[i], u.bx, u.by))
				continue;
            vis[next.bx][next.by][next.mx][next.my] = 1;
            q.push(next);
		}
	}
	printf("-1\n");
}
int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
        input();
        bfs();
	}
	return 0;
}