#2467. 推箱子

推箱子

Description

想象一下,你站在一个由方格组成的二 维迷宫里,这些格子可能被填满岩石,也可能没被填满岩石。你可以一 步一个格子地往北、往南、往东或往西移动。这样的动作叫作“走”。 其中一个空单元格包含一个箱子,你可以站在箱子旁边,推动箱子到相 邻的自由单元格。这样的动作叫作“推”。箱子除了用推的方式,不能 移动,如果你把它推到角落里,就再也不能把它从角落里拿出来了。将 其中一个空单元格标记为目标单元格。你的工作是通过一系列走和推把 箱子带到目标格子里。由于箱子很重,所以要尽量减少推的次数。编写 程序,计算最好的移动(走和推)顺序。

image

Format

Input

输入包含多个测试用例。每个测试用例的第11行都包含两个 整数rrcc (均小于或等于2020),表示迷宫的行数和列数。接下来是rr 行,每行都包含cc 个字符,每个字符都描述迷宫中的一个格子,对被填 满岩石的格子用“#”表示,对空格用“.”表示。对起始位置 用“S”表示,对箱子的起始位置用“B”表示,对目标单元格 用“T”表示。输入端以两个00终止。

Output

对于输入中的每个迷宫,都首先输出迷宫的编号。如果无 法将箱子带到目标单元格里,则输出“Impossible.”,否则输出一个 最小推送次数的序列。如果有多个这样的序列,则请选择一个最小总移 动(走和推)次数的序列。如果仍然有多个这样的序列,则任何一个都 可被接受。将序列输出为由字符NSEWnseN、S、E、W、n、s、eww组成的字符 串,大写字母表示推,小写字母表示走,字母分别表示北、南、东和西 这44个方向。在每个测试用例之后都输出一个空行。

Samples

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

来源

POJ1475