3488. [POJ 1475]推箱子

【题目描述】

想象一下你站在一个二维迷宫里，这个迷宫由正方形的单元组成，这个迷宫可能被石头填满，也可能没有。你可以一步一个单元地向北、向南、向东或向西移动。            

 迷宫中有一个盒子，这个盒子不能用其他方式移动，只能用推的方式，这意味着如果你把它推到角落里，你就再也不能把它从角落里拿出来了。            

其中一个空单元格被标记为目标单元格。你的任务是通过一系列的行走和推送把盒子带到目标单元。由于箱子很重，你要尽量减少推的次数。你能写一个程序来计算出最优序列吗？

【输入格式】

输入包含几个迷宫的描述。

每个迷宫描述以一行包含两个整数r和c（r,c<=20）开始，表示迷宫的行数和列数。             

下面是r行，每行包含c个字符。每个字符描述了迷宫的一个细胞。被石头填满的单元格用“#”表示，空单元格用“.”表示。您的起始位置用“S”表示，方框的起始位置用“B”表示，目标单元格用“T”表示。r和c的输入以两个零结束。

【输出格式】

首先打印迷宫的编号，如示例输出所示。

然后，如果无法将盒子带到目标单元格，请打印“Impossible”。              

否则，输出一个最小的推箱子序列。

多解时，先最小化箱子被推动的次数，再最小化人移动的步数。若仍有多条路线，则按照N、S、W、E的顺序优先选择箱子的移动方向（即先上下推，再左右推）。在此前提下，再按照n、s、w、e的顺序优先选择人的移动方向（即先上下动，再左右动）。

 将序列打印为一个由字符N、S、E、W、n、s、e和w组成的字符串，其中大写字母代表推盒子方向，小写字母代表行走方向，N表示北，S表示南，E表示东，W表示西，上北下南左西右东。

在每组结果后面输出一行空白行。

【样例输入】

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