174. 推箱子

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

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

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

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

推箱子.jpg

输入格式

输入包含多个测试用例。

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

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

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

输出格式

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

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

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

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

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

数据范围

$1 \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