本来只是打算为今晚的CF热热手的，结果选了道坑爹的BFS。写了350多行的代码还WA了一次。。。。。
对于普通的方格有五种情况，如下图所示，对于方格5来说，与1，与2，与3，与4组成的矩形为四种不同的情况，还有一种为竖直站立的情况。
对于Easily Broken Cell只存在前四种情况。
很显然第三维标记这几种情况即可。思路还算简单，代码写的比较麻烦了。。。。
话说今年大年三十哇，出去耍会先。
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cmath>
#include <algorithm>
#define LL long long
#define PI (acos(-1.0))
#define EPS (1e-8)
using namespace std;
const int MAXN = 1001000;
bool mark[510][510][5];
char Map[510][510];
struct N
{
int x,y,ty,ans;
};
int jx[] = {-1, 0, 1, 0};
int jy[] = { 0,-1, 0, 1};
void bfs(int n,int m)
{
int i,j;
queue<N> q;
N s,t;
memset(mark,false,sizeof(mark));
for(i = 1,j = m+1;i < n && j == m+1; ++i)
{
for(j = 1;j <= m && Map[i][j] != ‘X‘; ++j)
;
}
s.x = i-1,s.y = j;
for(i = 0;i < 4 && Map[s.x+jx[i]][s.y+jy[i]] != ‘X‘; ++i)
;
s.ty = i;
s.ans = 0;
mark[s.x][s.y][s.ty] = true;
q.push(s);
while(q.empty() == false)
{
s = q.front();
q.pop();
if(Map[s.x][s.y] == ‘O‘ && s.ty == 4)
{
cout<<s.ans<<endl;
return ;
}
if(s.ty == 0)
{
if(s.x-2 >= 1 && Map[s.x-2][s.y] != ‘#‘ && Map[s.x-2][s.y] != ‘E‘ && mark[s.x-2][s.y][4] == false)
{
t.ty = 4;
t.x = s.x-2;
t.y = s.y;
t.ans = s.ans + 1;
mark[s.x-2][s.y][4] = true;
q.push(t);
}
if(s.x+1 <= n && Map[s.x+1][s.y] != ‘#‘ && Map[s.x+1][s.y] != ‘E‘ && mark[s.x+1][s.y][4] == false)
{
t.ty = 4;
t.x = s.x+1;
t.y = s.y;
t.ans = s.ans+1;
mark[s.x+1][s.y][4] = true;
q.push(t);
}
if(s.y+1 <= m && s.x-1 >= 1 && Map[s.x][s.y+1] != ‘#‘ && Map[s.x-1][s.y+1] != ‘#‘ && mark[s.x][s.y+1][0] == false && mark[s.x-1][s.y+1][2] == false)
{
t.ty = 0;
t.x = s.x;
t.y = s.y+1;
t.ans = s.ans+1;
mark[s.x][s.y+1][0] = true ;
mark[s.x-1][s.y+1][2] = true ;
q.push(t);
}
if(s.y-1 >= 1 && s.x-1 >= 1 && Map[s.x][s.y-1] != ‘#‘ && Map[s.x-1][s.y-1] != ‘#‘ && mark[s.x][s.y-1][0] == false && mark[s.x-1][s.y-1][2] == false)
{
t.ty = 0;
t.x = s.x;
t.y = s.y-1;
t.ans = s.ans+1;
mark[s.x][s.y-1][0] = true ;
mark[s.x-1][s.y-1][2] = true ;
q.push(t);
}
}
else if(s.ty == 1)
{
if(s.y-2 >= 1 && Map[s.x][s.y-2] != ‘#‘ && Map[s.x][s.y-2] != ‘E‘ && mark[s.x][s.y-2][4] == false)
{
t.ty = 4;
t.x = s.x;
t.y = s.y-2;
t.ans = s.ans + 1;
mark[s.x][s.y-2][4] = true;
q.push(t);
}
if(s.y+1 <= m && Map[s.x][s.y+1] != ‘#‘ && Map[s.x][s.y+1] != ‘E‘ && mark[s.x][s.y+1][4] == false)
{
t.ty = 4;
t.x = s.x;
t.y = s.y+1;
t.ans = s.ans+1;
mark[s.x][s.y+1][4] = true;
q.push(t);
}
if(s.y-1 >= 1 && s.x+1 <= n && Map[s.x+1][s.y] != ‘#‘ && Map[s.x+1][s.y-1] != ‘#‘ && mark[s.x+1][s.y][1] == false && mark[s.x+1][s.y-1][3] == false)
{
t.ty = 1;
t.x = s.x+1;
t.y = s.y;
t.ans = s.ans+1;
mark[s.x+1][s.y][1] = true ;
mark[s.x+1][s.y-1][3] = true ;
q.push(t);
}
if(s.y-1 >= 1 && s.x-1 >= 1 && Map[s.x-1][s.y] != ‘#‘ && Map[s.x-1][s.y-1] != ‘#‘ && mark[s.x-1][s.y][1] == false && mark[s.x-1][s.y-1][3] == false)
{
t.ty = 1;
t.x = s.x-1;
t.y = s.y;
t.ans = s.ans+1;
mark[s.x-1][s.y][1] = true ;
mark[s.x-1][s.y-1][3] = true ;
q.push(t);
}
}
else if(s.ty == 2)
{
if(s.x-1 >= 1 && Map[s.x-1][s.y] != ‘#‘ && Map[s.x-1][s.y] != ‘E‘ && mark[s.x-1][s.y][4] == false)
{
t.ty = 4;
t.x = s.x-1;
t.y = s.y;
t.ans = s.ans + 1;
mark[s.x-1][s.y][4] = true;
q.push(t);
}
if(s.x+2 <= n && Map[s.x+2][s.y] != ‘#‘ && Map[s.x+2][s.y] != ‘E‘ && mark[s.x+2][s.y][4] == false)
{
t.ty = 4;
t.x = s.x+2;
t.y = s.y;
t.ans = s.ans+1;
mark[s.x+2][s.y][4] = true;
q.push(t);
}
if(s.y+1 <= m && s.x+1 <= n && Map[s.x][s.y+1] != ‘#‘ && Map[s.x+1][s.y+1] != ‘#‘ && mark[s.x][s.y+1][2] == false && mark[s.x+1][s.y+1][0] == false)
{
t.ty = 2;
t.x = s.x;
t.y = s.y+1;
t.ans = s.ans+1;
mark[s.x][s.y+1][2] = true ;
mark[s.x+1][s.y+1][0] = true ;
q.push(t);
}
if(s.y-1 >= 1 && s.x+1 <= n && Map[s.x][s.y-1] != ‘#‘ && Map[s.x+1][s.y-1] != ‘#‘ && mark[s.x][s.y-1][2] == false && mark[s.x+1][s.y-1][0] == false)
{
t.ty = 2;
t.x = s.x;
t.y = s.y-1;
t.ans = s.ans+1;
mark[s.x][s.y-1][2] = true ;
mark[s.x+1][s.y-1][0] = true ;
q.push(t);
}
}
else if(s.ty == 3)
{
if(s.y-1 >= 1 && Map[s.x][s.y-1] != ‘#‘ && Map[s.x][s.y-1] != ‘E‘ && mark[s.x][s.y-1][4] == false)
{
t.ty = 4;
t.x = s.x;
t.y = s.y-1;
t.ans = s.ans + 1;
mark[s.x][s.y-1][4] = true;
q.push(t);
}
if(s.y+2 <= m && Map[s.x][s.y+2] != ‘#‘ && Map[s.x][s.y+2] != ‘E‘ && mark[s.x][s.y+2][4] == false)
{
t.ty = 4;
t.x = s.x;
t.y = s.y+2;
t.ans = s.ans+1;
mark[s.x][s.y+2][4] = true;
q.push(t);
}
if(s.y+1 <= m && s.x+1 <= n && Map[s.x+1][s.y] != ‘#‘ && Map[s.x+1][s.y+1] != ‘#‘ && mark[s.x+1][s.y][3] == false && mark[s.x+1][s.y+1][1] == false)
{
t.ty = 3;
t.x = s.x+1;
t.y = s.y;
t.ans = s.ans+1;
mark[s.x+1][s.y][3] = true ;
mark[s.x+1][s.y+1][1] = true ;
q.push(t);
}
if(s.y+1 <= m && s.x-1 >= 1 && Map[s.x-1][s.y] != ‘#‘ && Map[s.x-1][s.y+1] != ‘#‘ && mark[s.x-1][s.y][3] == false && mark[s.x-1][s.y+1][1] == false)
{
t.ty = 3;
t.x = s.x-1;
t.y = s.y;
t.ans = s.ans+1;
mark[s.x-1][s.y][3] = true ;
mark[s.x-1][s.y+1][1] = true ;
q.push(t);
}
}
else if(s.ty == 4)
{
if(s.x-2 >= 1 && Map[s.x-1][s.y] != ‘#‘ && Map[s.x-2][s.y] != ‘#‘ && mark[s.x-1][s.y][0] == false && mark[s.x-2][s.y][2] == false)
{
t.ty = 0;
t.x = s.x-1;
t.y = s.y;
t.ans = s.ans+1;
mark[s.x-1][s.y][0] = true;
mark[s.x-2][s.y][2] = true;
q.push(t);
}
if(s.x+2 <= n && Map[s.x+1][s.y] != ‘#‘ && Map[s.x+2][s.y] != ‘#‘ && mark[s.x+1][s.y][2] == false && mark[s.x+2][s.y][0] == false)
{
t.ty = 2;
t.x = s.x+1;
t.y = s.y;
t.ans = s.ans+1;
mark[s.x+1][s.y][2] = true;
mark[s.x+2][s.y][0] = true;
q.push(t);
}
if(s.y-2 >= 1 && Map[s.x][s.y-1] != ‘#‘ && Map[s.x][s.y-2] != ‘#‘ && mark[s.x][s.y-1][1] == false && mark[s.x][s.y-2][3] == false)
{
t.ty = 1;
t.x = s.x;
t.y = s.y-1;
t.ans = s.ans+1;
mark[s.x][s.y-1][1] = true;
mark[s.x][s.y-2][3] = true;
q.push(t);
}
if(s.y+2 <= m && Map[s.x][s.y+1] != ‘#‘ && Map[s.x][s.y+2] != ‘#‘ && mark[s.x][s.y+1][3] == false && mark[s.x][s.y+2][1] == false)
{
t.ty = 3;
t.x = s.x;
t.y = s.y+1;
t.ans = s.ans+1;
mark[s.x][s.y+1][3] = true;
mark[s.x][s.y+2][1] = true;
q.push(t);
}
}
}
cout<<"Impossible"<<endl;
}
int main()
{
int i,n,m;
while(scanf("%d %d",&n,&m) && (n||m))
{
for(i = 1;i <= n; ++i)
{
scanf("%*c%s",Map[i]+1);
}
bfs(n,m);
}
return 0;
}