【HDOJ】2364 Escape

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <queue>
  5 using namespace std;
  6 
  7 #define MAXN 85
  8 
  9 typedef struct node_st {
 10     int x, y;
 11     int d, s;
 12     node_st() {}
 13     node_st(int xx, int yy, int dd, int ss) {
 14         x = xx; y = yy; d = dd; s = ss;
 15     }
 16 } node_st;
 17 
 18 char map[MAXN][MAXN];
 19 bool visit[4][MAXN][MAXN];
 20 int direct[4][2] = {-1,0,1,0,0,-1,0,1};
 21 int n, m;
 22 
 23 int bfs(int sx, int sy) {
 24     int i, j, nx, ny;
 25     queue<node_st> que;
 26     node_st node;
 27     bool flag;
 28 
 29     if (sx==0 || sx==n-1 || sy==0 || sy==m-1)
 30         return 0;
 31     memset(visit, false, sizeof(visit));
 32     visit[0][sx][sy] = visit[1][sx][sy] = visit[2][sx][sy] = visit[3][sx][sy] = true;
 33 
 34     for (i=0; i<4; ++i) {
 35         nx = sx + direct[i][0];
 36         ny = sy + direct[i][1];
 37         if (nx<0 || nx>=n || ny<0 || ny>=m)
 38             continue;
 39         if (map[nx][ny] != ‘#‘) {
 40             que.push(node_st(nx, ny, i, 1));
 41             visit[i][nx][ny] = true;
 42         }
 43     }
 44 
 45     while ( !que.empty() ) {
 46         node = que.front();
 47         que.pop();
 48         flag = true;
 49         // node.d = 0/1 -> south/north
 50         // node.d = 2/3 -> east/west
 51         j = (node.d&2) ? 0:2;
 52         for (i=j; i<j+2; ++i) {
 53             nx = node.x + direct[i][0];
 54             ny = node.y + direct[i][1];
 55             if (nx<0 || nx>=n || ny<0 || ny>=m)
 56                 continue;
 57             if (map[nx][ny] != ‘#‘) {
 58                 flag = false;
 59                 if (!visit[i][nx][ny]) {
 60                     if (nx==0 || nx==n-1 || ny==0 || ny==m-1)
 61                         return node.s+1;
 62                     que.push(node_st(nx, ny, i, node.s+1));
 63                     visit[i][nx][ny] = true;
 64                 }
 65             }
 66         }
 67         if (flag) {
 68             i = node.d;
 69             nx = node.x + direct[i][0];
 70             ny = node.y + direct[i][1];
 71             if (nx<0 || nx>=n || ny<0 || ny>=m)
 72                 continue;
 73             if (map[nx][ny]==‘#‘ || visit[i][nx][ny])
 74                 continue;
 75             if(nx==0 || nx==n-1 || ny==0 || ny==m-1)
 76                 return node.s+1;
 77             que.push(node_st(nx, ny, i, node.s+1));
 78             visit[i][nx][ny] = true;
 79         }
 80     }
 81     return -1;
 82 }
 83 
 84 int main() {
 85     int t, x, y;
 86     int i, j;
 87 
 88     scanf("%d", &t);
 89 
 90     while (t--) {
 91         scanf("%d %d", &n, &m);
 92         for (i=0; i<n; ++i) {
 93             scanf("%s", map[i]);
 94             for (j=0; j<m; ++j)
 95                 if (map[i][j] == ‘@‘) {
 96                     x = i;
 97                     y = j;
 98                 }
 99         }
100         printf("%d\n", bfs(x, y));
101     }
102 
103     return 0;
104 }