#2532. 推箱子

推箱子

说明

本题差SPJ,欢迎大家提供标准SPJ

题目描述

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

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

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

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

输入格式

输入包含多个测试用例。

对于每个测试用例,第一行包括两个整数 N,M。

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

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

输出格式

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

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

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

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

在此前提下,再按照 nswe 的顺序优先选择人的移动方向(即先上下动,再左右动)。

样例

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,M201≤N,M≤20

来源

  • POJ1475
  • 算法竞赛进阶指南