首页 > 试题广场 >

推箱子

[编程题]推箱子

热度指数：3144 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

大家一定玩过“推箱子”这个经典的游戏。具体规则就是在一个N*M的地图上，有1个玩家、1个箱子、1个目的地以及若干障碍，其余是空地。玩家可以往上下左右4个方向移动，但是不能移动出地图或者移动到障碍里去。如果往这个方向移动推到了箱子，箱子也会按这个方向移动一格，当然，箱子也不能被推出地图或推到障碍里。当箱子被推到目的地以后，游戏目标达成。现在告诉你游戏开始是初始的地图布局，请你求出玩家最少需要移动多少步才能够将游戏目标达成。

输入描述:

每个测试输入包含1个测试用例
第一行输入两个数字N，M表示地图的大小。其中0<N，M<=8。
接下来有N行，每行包含M个字符表示该行地图。其中 . 表示空地、X表示玩家、*表示箱子、#表示障碍、@表示目的地。
每个地图必定包含1个玩家、1个箱子、1个目的地。

输出描述:

输出一个数字表示玩家最少需要移动多少步才能将游戏目标达成。当无论如何达成不了的时候，输出-1。

示例1

输入

4 4
....
..*@
....
.X..
6 6
...#..
......
#*##..
..##.#
..X...
.@#...

输出

3
11

算法知识视频讲解

Python

周昆

from collections import deque
start = [0] * 4
end = [0] * 2
N, M = map(int, raw_input().split())
maze = []
for i in range(N):
	maze.append([])
	for j, s in enumerate(raw_input()):
		maze[i].append(s)
		if s == '*':
			start[0], start[1] = i, j
		elif s == 'X':
			start[2], start[3] = i, j
		elif s =='@':
			end[0], end[1] = i, j
# box_x, box_y, per_x, per_y
reach = [[[[-1 for _ in range(M)] for _ in range(N)] for _ in range(M)] for _ in range(N)]
mazeQueue = deque()
mazeQueue.append(start)
direction = ((0, 1), (1, 0), (0, -1), (-1, 0))
reach[start[0]][start[1]][start[2]][start[3]] = 0
while len(mazeQueue):
	point = mazeQueue.popleft()
	if point[0]  == end[0] and point[1] == end[1]:
		print reach[point[0]][point[1]][point[2]][point[3]]
		break
	for i in range(4):
		# new coordinate for person
		xper = point[2]+direction[i][0]
		yper = point[3]+direction[i][1]
		# check validity 
		if 0 <= xper < N and 0 <= yper < M and maze[xper][yper] != "#":
			if xper == point[0] and yper == point[1]:
				xbox, ybox = point[0] + direction[i][0], point[1] + direction[i][1]
				if xbox < 0 or xbox >= N or ybox < 0 or ybox >= M or maze[xbox][ybox] == '#':
					continue
			else:
				xbox, ybox = point[0], point[1]
			if reach[xbox][ybox][xper][yper] < 0:
				mazeQueue.append([xbox, ybox, xper, yper])
				reach[xbox][ybox][xper][yper] = reach[point[0]][point[1]][point[2]][point[3]] + 1
if point[0]  != end[0] or point[1] != end[1]:
	print -1

发表于 2017-05-05 09:45:01 回复(0)