#69. 「Pushing Boxes」 推箱子

「Pushing Boxes」 推箱子

推箱子游戏相信大家都不陌生,在本题中,你将控制一个人把1个箱子到目的地。

给定一张N行M列的地图,用字符”.”表示空地,字符”#”表示墙,字符”S”表示人的起始位置,字符”B”表示箱子的起始位置,字符”T”表示箱子的目标位置。

求一种移动方案,使箱子移动的次数最少,在此基础上再让人移动的总步数最少。

方案中使用大写的“EWSN”(东西南北)表示箱子的移动,使用小写的“ewsn”(东西南北)表示人的移动。

推箱子.jpg

输入格式

输入包含多个测试用例。

对于每个测试用例,第一行包括两个整数N,M。

接下来N行,每行包括M个字符,用以描绘整个N行M列的地图。

当样例为N=0,M=0时,表示输入终止,且该样例无需处理。

输出格式

对于每个测试用例,第一行输出”Maze #”+测试用例的序号。

第二行输入一个字符串,表示推箱子的总体移动过程,若无解,则输出”Impossible.”。

每个测试用例输出结束后输出一个空行。

若有多条路线满足题目要求,则按照N、S、W、E的顺序优先选择箱子的移动方向(即先上下推,再左右推)。

在此前提下,再按照n、s、w、e的顺序优先选择人的移动方向(即先上下动,再左右动)。

数据范围

1N,M201 \le N,M \le 20

输入样例:

1 7
SB....T
1 7
SB..#.T
7 11
###########
#T##......#
#.#.#..####
#....B....#
#.######..#
#.....S...#
###########
8 4
....
.##.
.#..
.#..
.#.B
.##S
....
###T
0 0

输出样例:

Maze #1
EEEEE

Maze #2
Impossible.

Maze #3
eennwwWWWWeeeeeesswwwwwwwnNN

Maze #4
swwwnnnnnneeesssSSS

来源

  • 《算法竞赛进阶指南》
  • acwing 可能含有视频讲解