題目：
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.
輸入：
nput 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.
樣例輸入：
7 7
#######
#..X###
#..##O#
#....E#
#....E#
#.....#
#######
0 0 樣例輸出：
10
想必這個遊戲大家都玩過把，就是把這個方塊通過翻滾到達指定的位置。
三種不同的狀态時它所進行的翻滾方式是不一樣的。細節在代碼中會标注。
AC代碼：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int r,c;
int sx,sy,ex,ey,sz;
char ch[505][505];
int vis[500][500][4];
//初始化這個地方詳細說明一下，第一個大括号表示狀态為0時可以操作的方式，第二個是為1時，第三個是為2
//時。立着的時候兩個方塊的坐标時一樣的，是以記錄一個就行；橫着的時候，是兩個XX相鄰，（這裡需要對
//應main函數），如果讓右邊的X變成“.”,那我們就記錄左邊的點，反之則記錄右邊的點。豎着的時候和橫着
//類似，就不再贅述了。
//int dx[3][4]={{-2,1,0,0},{-1,2,0,0},{0,0,-1,1}};//這個初始化是橫着标記左邊，豎着标記下邊
//int dy[3][4]={{0,0,-2,1},{0,0,1,-1},{-1,2,0,0}};
//int ds[3][4]={{1,1,2,2},{0,0,1,1},{0,0,2,2}};
int dx[3][4]={{-2,1,0,0},{-1,2,0,0},{0,0,-1,1}};//這個地方是橫着标記左邊，豎着标記上邊
int dy[3][4]={{0,0,2,-1},{0,0,1,-1},{1,-2,0,0}};
int ds[3][4]={{1,1,2,2},{0,0,1,1},{0,0,2,2}};
struct node
{
int x,y,state,step;//0代表立着，1代表橫着，2代表豎着，橫着記錄最左邊點的坐标，豎着記錄上面點的坐标
};
int check(node a)//判斷是否在區域内，并且是相應類型的方格
{ if(a.state==0 &&!(a.x>r||a.x<1||a.y>c||a.y<1)&&!vis[a.x][a.y][a.state]&&ch[a.x][a.y]!='E'&&ch[a.x][a.y]!='#')
return 0;
if(a.state==1 &&!(a.x<1||a.x+1>r||a.y<1||a.y>c)&&!vis[a.x][a.y][a.state]&&ch[a.x][a.y]!='#'&&ch[a.x+1][a.y]!='#')
return 0;
if(a.state==2&&!(a.x<1||a.x>r||a.y<1||a.y-1>c)&&!vis[a.x][a.y][a.state]&&ch[a.x][a.y]!='#'&&ch[a.x][a.y-1]!='#')
return 0;
return 1;
}
int bfs()
{
memset(vis,0,sizeof(vis));
queue<node>q;
while(q.size())q.pop();
node e;
e.x=sx;
e.y=sy;
e.state=sz;
e.step=0;
q.push(e);
vis[e.x][e.y][e.state]=1;
while(!q.empty())
{
e=q.front();
q.pop();
if(e.x==ex &&e.y==ey &&!e.state)return e.step;
for(int i=0;i<4;i++)
{
node f;
f.x=e.x+dx[e.state][i];
f.y=e.y+dy[e.state][i];
f.state=ds[e.state][i];
f.step=e.step+1;
if(check(f)) continue;
else
{
q.push(f);
vis[f.x][f.y][f.state]=1;
}
}
}
return -1;
}
int main()
{
while(scanf("%d%d",&r,&c)!=EOF && r+c)
{
for(int i=0;i<r;i++)
scanf("%s",ch[i]);
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
if(ch[i][j]=='X'&&ch[i][j-1]=='X')
{
sx=i;
sy=j;
ch[i][j-1]='.';
sz=2;
}
else if(ch[i][j]=='X'&&ch[i+1][j]=='X')
{
ch[i+1][j]='.';
sx=i;sy=j;
sz=1;
}
else if(ch[i][j]=='X')
{
sx=i;
sy=j;
sz=0;
}
else if(ch[i][j]=='O')
{
ex=i;
ey=j;
}
}
}
int ans=bfs();
if(ans == -1)printf("Impossible\n");
else printf("%d\n",ans);
}
return 0;
}