UVA589 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（西）表示步行操作。

请在两组测试数据之间输出额外的一行空行。

输入输出样例 #1

输入 #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

说明/提示

$R,C \leq 20$。