HDU 3713 Double Maze

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3713

题目：两个小球同时在两个迷宫里走，求使两个小球同时到达终点的最短走法。小球不能越出迷宫界，也不能掉到洞里。有的格子有挡板，如果挡板阻碍了小球的移动，则小球会呆在原地不动。如果有多组解，输出字典序最小的那个。

分析：裸BFS，但是我错了很多遍，因为之前有些地方没想清楚。

1，一开始我把 [小球被挡板阻碍] 和 [小球越界，小球掉到洞里] 放到一起考虑，写了个判断，都认为它们是不可达的。这是错误的。实际上这是两种情况，因为题目中有说：The barriers may make the commands take no effect, i.e., the ball does NOT move if there is a barrier on the way. 挡板只是抵消了这一步的命令，它可以继续执行下一步命令，并不是不可达。而[小球越界，小球掉到洞里] 才是不可达的情况。所以应当先判断这一步命令对两个小球是否分别有效，再判断它们是否越界或掉到洞里。

2，在判断小球能否移动到下一个格子上，有一个比较坑爹的地方。

举例说明：如果小球所在的格子是A，B是A正上方的格子，若A上方有挡板，那么它是不能由A直接向上移动到B。

我是先把小球移动到B，再判断B正下方是否有挡板，若有，则它是不能由A直接向上移动到B。

按理说这两种判断方式应该是一样的，也就是说，A上方有挡板=B下方有挡板。但事实上只有第一种判断方法是正确的，第二种是错误的，我WA了好几次才该对。

也就是说A上方有挡板≠B下方有挡板，至于为啥，貌似题目里面也没说清楚。

  1 #include <cstdio>
  2 #include <cstring>
  3 
  4 const int MAXN = 8;
  5 const int MAXSIZE = 10000 + 1;
  6 const char move[5] = "DLRU";   //保证字典序最小
  7 const int dx[] = { 1, 0, 0, -1 };
  8 const int dy[] = { 0, -1, 1, 0 };
  9 
 10 int map1[MAXN][MAXN];
 11 int map2[MAXN][MAXN];
 12 int start_x1, start_y1, start_x2, start_y2;
 13 int fa[MAXSIZE];         //记录移动路线
 14 bool vis[MAXSIZE];       //判重
 15 int queue[MAXSIZE];      //队列
 16 int dir[MAXSIZE];        //记录移动方向
 17 char answer[MAXSIZE];    //记录答案
 18 
 19 int GetHash( int a, int b, int c, int d )
 20 {
 21     return a * 1000 + b * 100 + c * 10 + d;
 22 }
 23 
 24 bool check( int x, int y, int dirc, int (*map)[8] )      //判断是否移动成功
 25 {
 26     if ( dirc == 3 && (( map[x][y] >> 3 ) & 1 ))      return false;
 27     if ( dirc == 2 && (( map[x][y] >> 2 ) & 1 ))      return false;
 28     if ( dirc == 1 &&  ( map[x][y] & 1 ) )            return false;
 29     if ( dirc == 0 && (( map[x][y] >> 1 ) & 1 ))      return false;
 30     return true;
 31 }
 32 
 33 bool in( int x, int y, int (*map)[8] )       //判断是否越界，是否掉到洞里
 34 {
 35     if ( x >= 1 && x <= 6 && y >= 1 && y <= 6 ) return ( ( map[x][y] >> 4 ) & 1 );
 36     return false;
 37 }
 38 
 39 int BFS()
 40 {
 41     //初始化
 42     memset( vis, false, sizeof(vis) );
 43 
 44     int front = 0, rear = 0;
 45     int hash = GetHash( start_x1, start_y1, start_x2, start_y2 );
 46     queue[ rear++ ] = hash;   //头结点入队
 47     vis[hash] = true;
 48     fa[hash] = 0;
 49 
 50     while ( front < rear )
 51     {
 52         int temp = queue[front];
 53 
 54         int x1 = temp / 1000;
 55         int y1 = ( temp / 100 ) % 10;
 56         int x2 = ( temp / 10 ) % 10;
 57         int y2 = temp % 10;
 58 
 59         if ( ( ( map1[x1][y1] >> 6 ) & 1 ) && ( ( map2[x2][y2] >> 6 ) & 1 ) ) return temp;   //判断终点
 60 
 61         for ( int i = 0; i < 4; i++ )    //四方向移动
 62         {
 63             int xx1 = x1;
 64             int yy1 = y1;
 65 
 66             if ( check(xx1, yy1, i, map1) )
 67             {
 68                 xx1 += dx[i];
 69                 yy1 += dy[i];
 70             }
 71 
 72             int xx2 = x2;
 73             int yy2 = y2;
 74 
 75             if ( check(xx2, yy2, i, map2) )
 76             {
 77                 xx2 += dx[i];
 78                 yy2 += dy[i];
 79             }
 80 
 81             if ( !in(xx1, yy1, map1) || !in( xx2, yy2, map2 ) ) continue;
 82 
 83             hash = GetHash( xx1, yy1, xx2, yy2 );
 84 
 85             if ( !vis[hash] )   //如果该节点尚未访问，插入队列
 86             {
 87                 queue[ rear++ ] = hash;
 88                 fa[hash] = temp;
 89                 dir[hash] = i;
 90                 vis[hash] = true;
 91             }
 92         }
 93         ++front;
 94     }
 95     return -1;      //如果查找失败，返回-1
 96 }
 97 
 98 int main()
 99 {
100     int T;
101     scanf( "%d", &T );
102     for ( int i = 1; i <= 6; i++ )
103         for ( int j = 1; j <= 6; j++ )
104         {
105             scanf( "%d", &map2[i][j] );
106             if ( ( map2[i][j] >> 5 ) & 1 )
107             {
108                 start_x2 = i;
109                 start_y2 = j;
110             }
111         }
112 
113     --T;
114     while ( T-- )
115     {
116         memcpy( map1, map2, sizeof(map1) );
117         start_x1 = start_x2;
118         start_y1 = start_y2;
119 
120         for ( int i = 1; i <= 6; i++ )
121             for ( int j = 1; j <= 6; j++ )
122             {
123                 scanf( "%d", &map2[i][j] );
124                 if ( ( map2[i][j] >> 5 ) & 1 )
125                 {
126                     start_x2 = i;
127                     start_y2 = j;
128                 }
129             }
130 
131         int ans = BFS();
132         if ( ans == -1 ) puts("-1");
133         else
134         {
135             int k = -1;
136             for( int i = ans; fa[i] != 0; i = fa[i] )
137                 answer[ ++k ] = move[ dir[i] ];
138 
139             for ( ; k >= 0; k-- ) putchar( answer[k] );
140             putchar('\n');
141         }
142     }
143     return 0;
144 }