POJ3322 Bloxorz I

暴搜，next数组与处理一下（小技巧）

 #include <cstdio>

 #include <iostream>

 #include <cstring>

 #include <cmath>

 #include <queue>

 #include <algorithm>

 using namespace std;

 #define res register int

 const int N=;

 char s[N][N];

 int n,m,d[N][N][];

 struct node{int x,y,lie;};//lie=0 立 lie=1 横向躺 lie=2 纵向躺

 node st,ed;

 queue<node> q;

 const int dx[]={,,-,},dy[]={-,,,};

 inline bool valid(int x,int y){

     return x>&&x<=n&&y>&&y<=m;

 }

 inline void read()

 {

     for(res i= ; i<=n ; i++)

         for(res j= ; j<=m ; j++) cin>>s[i][j];

     for(res i= ; i<=n ; i++)

         for(res j= ; j<=m ; j++)

         {

             if(s[i][j]=='O') ed.x=i,ed.y=j,ed.lie=,s[i][j]='.';

             else if(s[i][j]=='X')

             {

                 for(res k= ; k< ; k++)

                 {

                     int x=i+dx[k],y=j+dy[k];

                     if(valid(x,y) && s[x][y] == 'X') {

                         st.x=min(i,x),st.y=min(j,y),st.lie=k<?:;

                         s[i][j]=s[x][y]='.';

                         break;

                     }

                     if(s[i][j]=='X') st.x=i,st.y=j,st.lie=,s[i][j]='.';

                 }

             }

         }

 }

 const int next_x[][]={{,,-,},{,,-,},{,,-,}};

 const int next_y[][]={{-,,,},{-,,,},{-,,,}};

 const int next_lie[][]={{,,,},{,,,},{,,,}};

 inline bool valid(node t)

 {

     if(!valid(t.x,t.y)) return false;

     int nx=t.x,ny=t.y;

     if(s[nx][ny]=='#') return false;

     if(t.lie== && s[nx][ny]!='.') return false;

     if(t.lie== && s[nx][ny+]=='#') return false;

     if(t.lie== && s[nx+][ny]=='#') return false;

     return true;

 }

 inline int bfs()

 {

     for(res i= ; i<=n ; i++)

         for(res j= ; j<=m ; j++)

             for(res k= ; k< ; k++)    d[i][j][k]=-;

     while(q.size()) q.pop();

     d[st.x][st.y][st.lie]=; q.push(st);

     while(q.size())

     {

         node now=q.front(); q.pop();

         for(res i= ; i< ; i++)

         {

             node t;

             t.x=now.x+next_x[now.lie][i];

             t.y=now.y+next_y[now.lie][i];

             t.lie=next_lie[now.lie][i];

             if(!valid(t)) continue;

             if(d[t.x][t.y][t.lie]==-)

             {

                 d[t.x][t.y][t.lie]=d[now.x][now.y][now.lie]+;

                 q.push(t);

                 if(t.x==ed.x && t.y==ed.y && t.lie==ed.lie)

                     return d[t.x][t.y][t.lie];

             }

         }

     }

     return -;

 }

 int main()

 {

     while(scanf("%d %d",&n,&m)== && n && m)

     {

         read();

         int ans=bfs();

         if(ans==-) puts("Impossible");

         else printf("%d\n",ans);

     }

     return ;

 }