题目：
http://poj.org/problem?id=3322BFS
方块有三个状态要分开处理：立着的 横躺的（坐标记录左边那块） 竖躺的（坐标记录上边那块）
1 #include <iostream>
2 #include <cstdlib>
3 #include <cstdio>
4 #include <cstring>
5 using namespace std;
6 const int MaxN=510;
7 //0表示立 1表示横着躺（坐标为左边块坐标） 2表示竖着躺（坐标为上面块坐标）
8 const int dx[3][4]={{ 0,0,-2,1},
9 { 0,0,-1,1},
10 { 0,0,-1,2}};
11 const int dy[3][4]={{-2,1, 0,0},
12 {-1,2, 0,0},
13 {-1,1, 0,0}};
14 const int di[3][4]={{ 1,1, 2,2},
15 { 0,0, 1,1},
16 { 2,2, 0,0}};
17
18 int n,m;
19 char a[MaxN][MaxN];
20 int q[MaxN*MaxN][4];
21 bool v[MaxN][MaxN][3];
22
23 bool pd(int x,int y,int z)
24 {
25 if (x<0 || x>=n || y<0 || y>=m || v[x][y][z]==1) return 0;
26 if (z==0)
27 {
28 if (a[x][y]=='X' || a[x][y]=='O' || a[x][y]=='.')
29 {
30 return 1;
31 }
32 else
33 {
34 return 0;
35 }
36 }
37 if (z==1)
38 {
39 if (a[x][y]=='#' || a[x][y+1]=='#')
40 {
41 return 0;
42 }
43 else
44 {
45 return 1;
46 }
47 }
48 if (z==2)
49 {
50 if (a[x][y]=='#' || a[x+1][y]=='#')
51 {
52 return 0;
53 }
54 else
55 {
56 return 1;
57 }
58 }
59 }
60
61 void bfs(int x,int y,int z,int endx,int endy)
62 {
63 int first=0,last=1;
64 q[0][0]=x;
65 q[0][1]=y;
66 q[0][2]=z;
67 q[0][3]=0;
68 v[x][y][z]=1;
69 for (;first!=last;first++)
70 {
71 int xx=q[first][0],yy=q[first][1],zz=q[first][2],ans=q[first][3];
72 if (xx==endx && yy==endy && zz==0)
73 {
74 printf("%d\n",ans);
75 return;
76 }
77 for (int i=0;i<4;i++)
78 {
79 int xxx=xx+dx[zz][i],yyy=yy+dy[zz][i],zzz=di[zz][i];
80 if (pd(xxx,yyy,zzz)==1)
81 {
82 q[last][0]=xxx;
83 q[last][1]=yyy;
84 q[last][2]=zzz;
85 q[last][3]=ans+1;
86 v[xxx][yyy][zzz]=1;
87 last++;
88 }
89 }
90 }
91 printf("Impossible\n");
92 }
93
94 int main()
95 {
96 for (scanf("%d%d",&n,&m);n!=0 && m!=0;scanf("%d%d",&n,&m))
97 {
98 int st1x=-1,st1y=-1,st2x=-1,st2y=-1,endx,endy;
99 memset(a,'\0',sizeof(a));
100 memset(v,0,sizeof(v));
101 memset(q,0,sizeof(q));
102 for (int i=0;i<n;i++)
103 {
104 for (int j=0;j<m;j++)
105 {
106 scanf(" %c",&a[i][j]);
107 if (a[i][j]=='O')
108 {
109 endx=i;
110 endy=j;
111 }
112 if (a[i][j]=='X')
113 {
114 if (st1x==-1 && st1y==-1)
115 {
116 st1x=i;
117 st1y=j;
118 }
119 else
120 {
121 st2x=i;
122 st2y=j;
123 }
124 }
125 }
126 }
127 int x,y,z;
128 if (st2x==-1 || st2y==-1)
129 {
130 x=st1x;
131 y=st1y;
132 z=0;
133 }
134 else
135 {
136 if (st1y+1==st2y)
137 {
138 x=st1x;
139 y=st1y;
140 z=1;
141 }
142 else
143 {
144 x=st1x;
145 y=st1y;
146 z=2;
147 }
148 }
149 bfs(x,y,z,endx,endy);
150 }
151 return 0;
152 }
153