Description

想象一下，你站在一个由方格组成的二 维迷宫里，这些格子可能被填满岩石，也可能没被填满岩石。你可以一 步一个格子地往北、往南、往东或往西移动。这样的动作叫作“走”。 其中一个空单元格包含一个箱子，你可以站在箱子旁边，推动箱子到相 邻的自由单元格。这样的动作叫作“推”。箱子除了用推的方式，不能 移动，如果你把它推到角落里，就再也不能把它从角落里拿出来了。将 其中一个空单元格标记为目标单元格。你的工作是通过一系列走和推把 箱子带到目标格子里。由于箱子很重，所以要尽量减少推的次数。编写 程序，计算最好的移动（走和推）顺序。

Format

Input

输入包含多个测试用例。每个测试用例的第$1$行都包含两个 整数$r$ 和$c$ （均小于或等于$20$），表示迷宫的行数和列数。接下来是$r$ 行，每行都包含$c$ 个字符，每个字符都描述迷宫中的一个格子，对被填 满岩石的格子用“#”表示，对空格用“.”表示。对起始位置 用“S”表示，对箱子的起始位置用“B”表示，对目标单元格 用“T”表示。输入端以两个$0$终止。

Output

对于输入中的每个迷宫，都首先输出迷宫的编号。如果无 法将箱子带到目标单元格里，则输出“Impossible.”，否则输出一个 最小推送次数的序列。如果有多个这样的序列，则请选择一个最小总移 动（走和推）次数的序列。如果仍然有多个这样的序列，则任何一个都 可被接受。将序列输出为由字符$N、S、E、W、n、s、e$和$w$组成的字符 串，大写字母表示推，小写字母表示走，字母分别表示北、南、东和西 这$4$个方向。在每个测试用例之后都输出一个空行。

Samples

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

来源

POJ1475