Time Limit: 1000MS Memory Limit: 65535KB 64bit IO Format: %I64d & %I64u

Description

Push Box is a classic puzzle game. This game play in a grid, there are five types of block in it, the player, the box, the hole, empty place, and the wall. In every step, player can move up, down, left, or right, if the target place is empty. Moreover, if a box in the target place, and the next place in that direction is empty, player can move to the target place, and then push the box to the next place. Remember, both of the player and boxes can’t move out of the grid, or you may assume that there is a wall suround the whole grid. The objective of this game is to push every box to a hole. Now, your problem is to find the strategy to achieve the goal with shortest steps, supposed there are exactly three boxes.

 

Input

The input consists of several test cases. Each test case start with a line containing two number, n, m(1 < n, m ≤ 8), the rows and the columns of grid. Then n lines follow, each contain exact m characters, representing the type of block in it. (for empty place, X for player, * for box, # for wall, @ for hole). Each case contain exactly one X, three *, and three @. The input end with EOF.

 

Output

You have to print the length of shortest strategy in a single line for each case. (-1 if no such strategy)

 

Sample Input

4 4

….

..*@

..*@

.X*@

 

6 6

…#@.

@..*..

#*##..

..##*#

..X…

.@#…

 

 

 

Sample Output

7

11

 

Source

“网新恩普杯”杭州电子科技大学程序设计邀请赛


思路:BFS。难点在于状态的表示,对这道题来说,一个“状态”应该是玩家和三个箱子的坐标,所以判重用vis数组就应该是八维的。解决了这个问题后,就考虑走的时候怎么操作,分两种情况:

  1. 下一步不是箱子,只要不是墙就能走;
  2. 下一步是箱子,走过去的同时还会把箱子往前推,就还要判断前面那一格是不是箱子或墙,如果是就不能走,如果不是就可以走,同时更新推的箱子的坐标。

AC代码:

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
int n, m;
char map[10][10];
struct pos
{
	int x, y;
};
struct node
{
	pos player, box[3];
	int step;
};
const int dx[] = {0, 0, 1, -1},
			dy[] = {1, -1, 0, 0};
node start;
queue <node> q;
bool vis[8][8][8][8][8][8][8][8];
void input()
{
	for (int i = 0; i < n; i++)
		scanf("%s", map[i]);
}
void pre()
{
	int boxcnt = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			if (map[i][j] == 'X')
			{
				start.player.x = i;
				start.player.y = j;
			}
			else if (map[i][j] == '*')
			{
				start.box[boxcnt].x = i;
				start.box[boxcnt++].y = j;
			}
		}
	start.step = 0;
	memset(vis, 0, sizeof(vis));
	while (!q.empty())
		q.pop();
}
bool achieve(node cur)
{
	for (int i = 0; i < 3; i++)
		if (map[cur.box[i].x][cur.box[i].y] != '@')
			return 0;
	return 1;
}
int is_box(node cur)
{
	for (int i = 0; i < 3; i++)
		if (cur.player.x == cur.box[i].x && 
			cur.player.y == cur.box[i].y)
			return i;
	return -1;
}
bool check(int x, int y)
{
	if (x < 0 || x >= n || y < 0 || y >= m || map[x][y] == '#')
		return 0;
	return 1;
}
bool canpush(node cur, int dir, int boxnum)
{
	int boxx = cur.player.x + dx[dir],
		boxy = cur.player.y + dy[dir];
	if (!check(boxx, boxy))
		return 0;
	for (int i = 0; i < 3; i++)
		if (i != boxnum && boxx == cur.box[i].x && boxy == cur.box[i].y)
			return 0;
	return 1;
}
void sethash(node cur)
{
	vis[cur.player.x][cur.player.y][cur.box[0].x][cur.box[0].y][cur.box[1].x][cur.box[1].y][cur.box[2].x][cur.box[2].y] = 1;
}
bool gethash(node cur)
{
	return vis[cur.player.x][cur.player.y][cur.box[0].x][cur.box[0].y][cur.box[1].x][cur.box[1].y][cur.box[2].x][cur.box[2].y];
}
void bfs()
{
	pre();
	q.push(start);
	sethash(start);
	while (!q.empty())
	{
		node u = q.front();
		q.pop();
		if (achieve(u))
		{
			printf("%d\n", u.step);
			return;
		}
		for (int i = 0; i < 4; i++)
		{
			node next = u;
			next.step = u.step + 1;
			next.player.x = u.player.x + dx[i];
			next.player.y = u.player.y + dy[i];
			if (!check(next.player.x, next.player.y))
				continue;
			int boxnum = is_box(next);
			if (boxnum != -1)
			{
				if (!canpush(next, i, boxnum))
					continue;
				next.box[boxnum].x = next.player.x + dx[i];
				next.box[boxnum].y = next.player.y + dy[i];
				if (gethash(next))
					continue;
				sethash(next);
				q.push(next);
			}
			else
			{
				if (gethash(next))
					continue;
				sethash(next);
				q.push(next);
			}
		}
	}
	printf("-1\n");
}
int main()
{
	while (scanf("%d%d", &n, &m) == 2)
	{
		input();
		bfs();
	}
	return 0;
}

 

分类: ACM/ICPC

发表评论

电子邮件地址不会被公开。 必填项已用*标注