You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

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$。