题目描述

Little Tom loves playing games. One day he downloads a little computer game called 'Bloxorz' which makes him excited. It's a game about rolling a box to a specific position on a special plane. Precisely, the plane, which is composed of several unit cells, is a rectangle shaped area. And the box, consisting of two perfectly aligned unit cube, may either lies down and occupies two neighbouring cells or stands up and occupies one single cell. One may move the box by picking one of the four edges of the box on the ground and rolling the box 90 degrees around that edge, which is counted as one move. There are three kinds of cells, rigid cells, easily broken cells and empty cells. A rigid cell can support full weight of the box, so it can be either one of the two cells that the box lies on or the cell that the box fully stands on. A easily broken cells can only support half the weight of the box, so it cannot be the only cell that the box stands on. An empty cell cannot support anything, so there cannot be any part of the box on that cell. The target of the game is to roll the box standing onto the only target cell on the plane with minimum moves.

The box stands on a single cell

The box lies on two neighbouring cells, horizontally

The box lies on two neighbouring cells, vertically

After Little Tom passes several stages of the game, he finds it much harder than he expected. So he turns to your help.

输入格式

Input contains multiple test cases. Each test case is one single stage of the game. It starts with two integers R and C(3 ≤ R, C ≤ 500) which stands for number of rows and columns of the plane. That follows the plane, which contains R lines and C characters for each line, with 'O' (Oh) for target cell, 'X' for initial position of the box, '.' for a rigid cell, '#' for a empty cell and 'E' for a easily broken cell. A test cases starts with two zeros ends the input.

It guarantees that

• There's only one 'O' in a plane.
• There's either one 'X' or neighbouring two 'X's in a plane.
• The first(and last) row(and column) must be '#'(empty cell).
• Cells covered by 'O' and 'X' are all rigid cells.

输出格式

For each test cases output one line with the minimum number of moves or "Impossible" (without quote) when there's no way to achieve the target cell.

题目大意

【题目描述】

小汤姆喜欢玩游戏。有一天，他下载了一个叫做“Bloxorz”的小电脑游戏，让他非常兴奋。这是一个关于将一个方块滚动到特定位置的游戏。准确地说，这个平面由几个单位单元格组成，是一个矩形形状的区域。而方块由两个完美对齐的单位立方体组成，可以躺下并占据两个相邻的单元格，也可以站立并占据一个单独的单元格。可以通过选择方块在地面上的四条边之一，并围绕该边旋转 90 度来移动方块，每次旋转算作一步。有三种类型的单元格，刚性单元格、易碎单元格和空单元格。刚性单元格可以支撑方块的全部重量，因此可以是方块所占据的两个单元格中的任意一个，也可以是方块完全站立在上面的单元格。易碎单元格只能支撑方块重量的一半，因此不能是方块完全站立在上面的唯一单元格。空单元格无法支撑任何东西，因此方块不可能部分位于该单元格上。游戏的目标是以最少的步数将站立的方块滚动到平面上唯一的目标单元格。

方块站在单个单元格上

方块横躺在两个相邻的单元格上

方块纵躺在两个相邻的单元格上

在小汤姆通过游戏的几个阶段后，他发现比他预期的要难得多。因此，他求助于你的帮助。

【输入格式】

输入包含多个测试案例。每个测试案例都是游戏的一个阶段。它以两个整数 R 和 C（3 ≤ R，C ≤ 500）开头，表示平面的行数和列数。接下来是平面，其中包含 R 行和每行的 C 个字符，其中 'O' 表示目标单元格，'X' 表示方块的初始位置，'.' 表示刚性单元格，'#' 表示空单元格，'E' 表示易碎单元格。一个测试案例以两个 0 结束输入。

保证：

• 平面上只有一个 'O'。
• 平面上要么有一个 'X'，要么有相邻的两个 'X'。
• 第一行（和最后一行）（以及第一列和最后一列）必须是 '#'（空单元格）。
• 'O' 和 'X' 覆盖的单元格都是刚性单元格。

【输出格式】

对于每个测试案例，输出一行表示移动的最小次数，或在无法达到目标单元格时输出 "Impossible"（不带引号）。

翻译来自于：ChatGPT

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

10