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 }