Source Code
Problem: 3322		User: fyq
Memory: 12844K		Time: 672MS
Language: G++		Result: Accepted

    * Source Code

      #include <cstdio>
      #include <cstring>
      #define maxn 501
      #define maxq 770001

      using namespace std;

      typedef struct node
      {
          int x,y,dir,step,fa;
      }node;

      const int dx[3][4] = {{1,0,-2,0},{1,0,-1,0},{2,0,-1,0}};
      const int dy[3][4] = {{0,-2,0,1},{0,2,0,-1},{0,1,0,-1}};
      const int dd[3][4] = {{2,1,2,1},{1,0,1,0},{0,2,0,2}};
      const int dtx[3] = {0,0,1};
      const int dty[3] = {0,1,0};

      node q[maxq+1];
      bool mark[maxn+1][maxn+1][3]={};
      int map[maxn+1][maxn+1];
      int n,m,sx,sy,ds,ex,ey;

      bool init()
      {
          scanf("%d%d\n",&n,&m);
          if (!n) return 0;
          char ch;
          bool found=0;
          for (int i=1;i<=n;i++)
              {
                  for (int j=1;j<=m;j++)
                      {
                          ch = getchar();
                          map[i][j] = 2;
                          if (ch=='#') map[i][j] = 0;
                          if ((ch=='X')&&(found)) 
                              {
                                  if (sx==i-1)
                                      ds = 2;
                                  else
                                      ds = 1;
                              }
                          if ((ch=='X')&&(!found)) 
                              {
                                  sx = i; sy = j;ds = 0; found = 1;
                              }
                          if (ch=='E') map[i][j] = 1;
                          if (ch=='O') {ex = i; ey = j;}
                      }
                  scanf("\n");
              }
          return 1;
      }

      bool avail(int x,int y,int dir)
      {
          if ((x>n)||(x<1)||(y>m)||(y<1)) return 0;
          if (!map[x][y]) return 0;
          if (!map[x+dtx[dir]][y+dty[dir]]) return 0;
          if (!dir)
              if (map[x][y]<2) return 0;
          return 1;
      }

      void print_path(int tail)
      {
          int k = tail;
          while (q[k].fa)
              {
                  printf("%d %d %d\n",q[k].x,q[k].y,q[k].dir);
                  k = q[k].fa;
              }
      }

      int work()
      {
          int head = 1,tail = 1;
          q[1].x = sx; q[1].y = sy; q[1].dir = ds; q[1].step = 0; q[1].fa = 0;
          int tx,ty,td,bx,by,bd;
          mark[sx][sy][ds] = 1;
          //printf("%d %d %d\n",sx,sy,ds);
          while (head<=tail)
              {
                  bx = q[head].x; by = q[head].y;
                  bd = q[head].dir;
                  for (int k=0;k<=3;k++)
                      {
                          tx = bx + dx[bd][k];
                          ty = by + dy[bd][k];
                          td = dd[bd][k];
                          if (avail(tx,ty,td))
                          if (!mark[tx][ty][td])
                              {
                                  mark[tx][ty][td] = 1;
                                  q[++tail].x = tx; q[tail].y = ty;
                                  q[tail].dir = td;
                                  q[tail].step = q[head].step + 1; q[tail].fa = head;
                                  if ((tx==ex)&&(ty==ey)&&(td==0))
                                      {
                                          //print_path(tail);
                                          return q[tail].step;
                                      }
                              }
                      }
                  head++;
              }
          return -1;
      }

      int main()
      {
          while (1)
              {
                  if (!init()) break;
                  //printf("sx:%d sy:%d sd:%d\n",sx,sy,ds);
                  memset(mark,0,sizeof(mark));
                  int ans = work();
                  if (ans!=-1) printf("%d\n",ans);
                  else printf("Impossible\n");
              }
          return 0;
      }

程序不长，没有优化，但是很容易理解，开了个常量表，大幅缩短程序。
wa的童鞋注意，要开501X501 ！ 
同时队列要开500*500*3+1 ！
一下是我的测试数据,第一组和最后一组是我手动从游戏里抠出来的，第二组是poj前人提供的，第三组是样例。
input:
12 17
#################
######......#####
######.##...#####
######.##.....###
#X.....#####....#
#####...####..O.#
#####...#####...#
#######.##..#####
#######.....#####
#######.....#####
########...######
#################
7 5
#####
#...#
#O..#
#...#
#..X#
#..X#
#####
7 7
#######
#..X###
#..##O#
#....E#
#....E#
#.....#
#######
11 16
################
####EEEEEEE#####
####EEEEEEE#####
#....#####...###
#...#######..###
#...#######..###
#.X.##....EEEEE#
#...##....EEEEE#
######.O.##EE.E#
######...##EEEE#
################
0 0 

ans :
35
6
10
28

鉴于犯了如此低级的错误，我决定写一下解题报告反省一下……
my blog ： http://wronganswer.spaces.live.com/blog/cns!283235DBBEF06FAE!257.entry

• 啊 起点不一定竖着？ (0) allen4053040allen 2011-08-06 20:33:03