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) ![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA589/d33446a08a4244cfb7aec9ce86c82cfa17d5eedd.png)

输入输出格式

输入格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA589/b148b8f8a826fc7ff10df483d0b8151c59c60043.png)

输出格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA589/1dadf6a5495004e555a45d227e6620a1d0a547a5.png)

输入输出样例

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