Pushing Boxes

### 题面翻译 想象你站在一个二维的迷宫里，迷宫由 $R$ 列 $C$ 行共 $R\times C$ 个方格组成，有些方格里是岩石（所以你与箱子不能走到这些格子上），而另外的则是空格子。你可以在一个空格子上向北（上）、南（下）、东（右）、西（左）移动到另外一个相邻的空格子上，这个操作叫做**步行**。 有一个空格子上放着一个箱子，你可以站在盒子旁边，向盒子的方向移动，使得你和箱子共同平移一格（当然平移到的地方不能有岩石）。我们把这样的操作叫做**推**。你只能用推的方式来移动箱子，这意味着，如果你把箱子推到了死角里，你就无法将它推出来了。 现在给定你的起始坐标、箱子的起始坐标和箱子要被推到的坐标，请你找出一个最优的推箱子的操作序列，或报告无解。具体地说： 1. 这个操作序列的**推**操作的次数是最少的。 2. 在满足 (1) 的条件下，若存在不止一个操作序列，则要求操作序列的**总操作次数**（包括**步行**操作和**推**操作）最少。 3. 若在满足 (1) (2) 的条件下，操作序列仍然不唯一，任意输出一个均可。 ### 输入格式 **本题存在多组数据。** 对于每组数据，第一行是两个整数 $R,C$，描述迷宫的行数和列数。 接下来 $R$ 行，每行 $C$ 个字符，每个字符描述一个格子： - `#` 表示有岩石的格子。 - `.` 表示空格子。 - `B` 表示箱子初始位置。**这是一个空格子。** - `S` 表示你的初始位置。**这是一个空格子。** - `T` 表示箱子目标位置。**这是一个空格子。** 每个测试点以 $R=C=0$ 结尾，无需处理该组数据。 ### 输出格式 对于每组数据，第一行是一个字符串 `Maze #d`，其中 **$\boldsymbol{d}$ 表示这是第几组数据。** 如果无解，在第二行输出 `Impossible`. 否则输出一个符合题目要求的最优的（见上）的操作序列。具体地说： 用大写的 `N`（北）、`S`（南）、`E`（东）、`W`（西）表示**推**操作。 用小写的 `n`（北）、`s`（南）、`e`（东）、`w`（西）表示**步行**操作。 **请在两组测试数据之间输出额外的一行空行。** ### 数据范围/提示 $R,C \leq 20$。 请特别注意输出格式。

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=530 [PDF](https://uva.onlinejudge.org/external/5/p589.pdf) 



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