题目描述

想象你正站在一个由方形格子组成的二维迷宫中，这些格子可能被岩石填满，也可能是空的。你可以向北、南、东或西移动一步，每次移动一格。这些移动称为“行走”。

其中一个空格子中有一个箱子，你可以通过站在箱子旁边的格子，然后朝箱子的方向移动来将箱子推到相邻的空格子中。这种移动称为“推动”。箱子只能通过推动来移动，这意味着如果你将箱子推到一个角落，就无法再将其推出去了。

其中一个空格子被标记为目标格子。你的任务是通过一系列的行走和推动，将箱子带到目标格子。由于箱子非常重，你希望尽量减少推动的次数。你能编写一个程序来计算出最优的操作序列吗？

输入格式

输入包含多个迷宫的描述。每个迷宫描述的第一行是两个整数 r 和 c（均 ≤ 20），表示迷宫的行数和列数。

接下来是 r 行，每行包含 c 个字符。每个字符描述迷宫中的一个格子。岩石格子用 # 表示，空格子用 . 表示。你的起始位置用 S 表示，箱子的起始位置用 B 表示，目标格子用 T 表示。

输入以两个 0 作为 r 和 c 的结束标志。

输出格式

对于每个迷宫，首先输出迷宫的编号，如样例所示。如果无法将箱子推到目标格子，输出 ``Impossible.''。

否则，输出一个推动次数最少的操作序列。如果有多个这样的序列，选择总移动次数（行走和推动）最少的序列。如果仍有多个序列，任意输出一个即可。

序列用字符串表示，包含字符 N, S, E, W, n, s, e, w，其中大写字母表示推动，小写字母表示行走，不同字母分别代表北、南、东、西方向。

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

样例输入 1

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

样例输出 1

Maze #1
EEEEE

Maze #2
Impossible.

Maze #3
eennwwWWWWeeeeeesswwwwwwwnNN

Maze #4
swwwnnnnnneeesssSSS

来源

1997年西南欧区域竞赛