#85. 推箱子

推箱子

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

推箱子游戏相信大家都不陌生,在本题中,你将控制一个人把1\red{1}个箱子到目的地。

给定一张N\red{N}M\red{M}列的地图,用字符”.\red{.}”表示空地,字符”#\red{\#}”表示墙,字符”S\red{S}”表示人的起始位置,字符”B\red{B}”表示箱子的起始位置,字符”T\red{T}”表示箱子的目标位置。

求一种移动方案,使箱子移动的次数最少,在此基础上再让人移动的总步数最少。

方案中使用大写的“EWSN”(东西南北)表示箱子的移动,使用小写的“ewsn”(东西南北)表示人的移动。

img

输入格式

输入包含多个测试用例。

对于每个测试用例,第一行包括两个整数NM\red{N,M}

接下来N\red{N}行,每行包括M\red{M}个字符,用以描绘整个N\red{N}M\red{M}列的地图。

当样例为N=0M=0\red{N=0,M=0}时,表示输入终止,且该样例无需处理。

输出格式

对于每个测试用例,第一行输出”Maze #”+测试用例的序号。

第二行输入一个字符串,表示推箱子的总体移动过程,若无解,则输出”Impossible.”

每个测试用例输出结束后输出一个空行。

若有多条路线满足题目要求,则按照NSWE\red{N、S、W、E}的顺序优先选择箱子的移动方向(即先上下推,再左右推)。

在此前提下,再按照nswe\red{n、s、w、e}的顺序优先选择人的移动方向(即先上下动,再左右动)。

样例

输入样例

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
Maze #4
swwwnnnnnneeesssSSS

提示

1N,M20\red{1≤N,M≤20}

寒假营测试

未参加
状态
已结束
规则
ACM/ICPC
题目
7
开始于
2022-1-22 13:45
结束于
2022-1-22 16:45
持续时间
3 小时
主持人
参赛人数
30