3484. [POJ 3322] 益智方块I

【题目描述】

Bloxorz是一个风靡世界的小游戏。Bloxorz的地图是一个N行M列的矩阵，每个位置可能是硬地（用"."表示）、易碎地面（用"E"表示）、禁地（用"#"表示）、起点（用"X"表示）或终点（用"O"表示）。

你的任务是操作一个1*1*2的长方体。

这个长方体在地面上有两种放置形式，“立”在地面上（1*1的面接触地面）或者“躺”在地面上（1*2的面接触地面）。

在每一步操作中，可以按上下左右四个键之一。按下之后，长方体向对应的方向沿着棱滚动90度。

任意时刻，长方体不能有任何部位接触禁地（否则就会掉下去），并且不能立在易碎地面上（否则会因为压强太大掉下去）。

"X"标识长方体的起始位置，地图上可能有一个"X"或者两个相邻的"X"。

地图上唯一的一个"O"标识目标位置。求把长方体移动到目标位置（即立在"O"上）所需要的最少步数。

如果无解，输出"Impossible"。在移动过程中，"X"和"O"标识的位置都可以看作是硬地被利用，3<=N,M<=500。

【输入格式】

输入包含多重测试数据。每个测试数据都是一个游戏棋盘。首先输入两个整数R和C（3 ≤ R, C ≤ 500），分别为这个游戏棋盘的行和列。

在这个平面中，有R行C列的字符。其中，‘O’代表目的地，‘X’代表箱子现在的位置，‘.’代表一个坚固的格子，‘#’代表空格子，‘E’代表一个易碎的格子。测试数据以两个0结尾。

该测试数据保证： 只有一个‘O’在平面中，只会有一个或两个相邻的‘X’在平面中，边缘上的格子必定是‘#’（空格子），‘O’和‘X’代表的格子必为坚固的格子

【输出格式】

对于每组测试数据，输出的必定是最小移动步数或者是‘Impossible’（当没有方法去到达目的地的格子时）。

【样例输入】

7 7
#######
#..X###
#..##O#
#....E#
#....E#
#.....#
#######
0 0

【样例输出】

10

【来源】

《算法竞赛进阶指南》POJ3322