Pushing Boxes

题意翻译

## 题目描述 想象一下,你站在一个二维的迷宫里,由方形的格子组成,可能有或者没有被岩石充满。你可以在一个格子上向北、南、东或西移动。这些动作叫做步行。 其中一个空格子包含一个盒子,它可以通过站在盒子旁边,然后在盒子的方向上移动,移动到相邻的空格子。这样的动作叫做推。这个盒子不能用任何其他方式来移动,这意味着如果你把它推到角落里,你就再也不能把它从角落里拿出来。 其中一个空格子被标记为目标格子。你的工作是把箱子放在目标格子中,通过一系列的行走和推动。由于箱子很重,你想把推的数量减到最少。你能写出一个程序来找出最好的顺序吗? ## 输入 输入包含几个迷宫的描述。每个迷宫描述都包含一个包含两个整数R和C的线段($R,C<=20$),表示迷宫的行数和列数。 下面是每个包含C字符的R行。每个字符描述迷宫中的一个单元。一个岩石的格子是由一个'#'表示的,一个空的格子由一个'.'表示。你的起始位置用“S”表示,方框的开始位置由“B”和目标格子按“T”表示。 输入R,C为0 0结束。 ## 输出 对于每一个迷宫中的输入,首先打印迷宫的数目,如样本输出所示。然后,如果不可能把盒子带到目标单元格,打印"Impossible."。 否则,输出一个最小化推送次数的序列。如果有不止一个这样的序列,那么选择一个最小化总移动次数(步行和推送)的序列。如果仍然有不止一个这样的序列,任何一个都是可以接受的。 将序列打印为字符N、S、E、W、n、s、e和w的字符串,其中大写字母代表推,小写字母代表行走,不同字母代表南北、南、东和西的方向。 在每个测试用例之后输出一个空行。 感谢@周子凯 提供翻译

题目描述

[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