推箱子游戏相信大家都不陌生,在本题中,你将控制一个人把1个箱子到目的地。
给定一张 N 行 M 列的地图,用字符 ”.” 表示空地,字符 ”#” 表示墙,字符 ”S” 表示人的起始位置,字符 ”B” 表示箱子的起始位置,字符 ”T” 表示箱子的目标位置。
求一种移动方案,使箱子移动的次数最少,在此基础上再让人移动的总步数最少。
方案中使用大写的 “EWSN” (东西南北)表示箱子的移动,使用小写的 “ewsn” (东西南北)表示人的移动。
输入包含多个测试用例。
对于每个测试用例,第一行包括两个整数 N,M , 。
接下来 N 行,每行包括 M 个字符,用以描绘整个 N 行 M 列的地图。
当样例为 N=0,M=0 , 时,表示输入终止,且该样例无需处理。
对于每个测试用例,第一行输出 ”Maze #” + 测试用例的序号。
第二行输入一个字符串,表示推箱子的总体移动过程,若无解,则输出 ”Impossible.” 。
每个测试用例输出结束后输出一个空行。
若有多条路线满足题目要求,则按照 N、S、W、E 、 、 、 的顺序优先选择箱子的移动方向(即先上下推,再左右推)。
在此前提下,再按照 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
1≤N,M≤20