1 #include <iostream>  2 #include <limits>  3 #include <queue>  4 using namespace std;  5   6 typedef pair<int, int> P;  7   8 char maze[41][41];   9 int dist[41][41]; 10 int spDirX[4] = {1, 0, -1, 0}; 11 int spDirY[4] = {0, 1, 0, -1}; 12 int n; 13 int w, h; 14 int startX, startY; 15 int endX, endY; 16 const int INF = numeric_limits<int>::max(); 17 int sp, lo, ro; 18 int dx[4] = { 19         0, 1, 0, -1 20 }; 21 int dy[4] = { 22         -1, 0, 1, 0     23 }; 24 void leftOrder(int x, int y, int sum, int dir) 25 { 26     //ÖÕÖ¹  27     if(x == endX && y == endY) 28     { 29         lo = sum; 30         return ; 31     } 32     //µÚÒ»¸öÔªËØÈ·¶¨·½Ïò 33     if(sum == 1) 34     { 35         for(int i = 0; i < 4; ++i) 36         { 37             int nx = x + dx[i]; 38             int ny = y + dy[i]; 39             if(nx >= 0 && nx < w && ny >= 0 && ny < h && maze[ny][nx] == ‘.‘) 40             { 41                     leftOrder(nx, ny , sum+1, i); 42                     break; 43             } 44              45         } 46     } 47     else 48     { 49         //Ò»°ãÇé¿ö  50         dir = (dir+3) % 4; 51         for(int i = 0; i < 4; ++i) 52         { 53             int nx = x + dx[(dir+i)%4]; 54             int ny = y + dy[(dir+i)%4]; 55             if(nx >= 0 && nx < w && ny >= 0 && ny < h && maze[ny][nx] != ‘#‘) 56             { 57                 leftOrder(nx, ny , sum+1, (dir+i)%4); 58                 break; 59             }         60         }     61     } 62      63 } 64  65 void rightOrder(int x, int y, int sum, int dir) 66 { 67         //ÖÕÖ¹  68     if(x == endX && y == endY) 69     { 70         ro = sum; 71         return ; 72     } 73     //µÚÒ»¸öÔªËØÈ·¶¨·½Ïò 74     if(sum == 1) 75     { 76         for(int i = 0; i < 4; ++i) 77         { 78             int nx = x + dx[i]; 79             int ny = y + dy[i]; 80             if(nx >= 0 && nx < w && ny >= 0 && ny < h && maze[ny][nx] == ‘.‘) 81             { 82                     rightOrder(nx, ny , sum+1, i); 83                     break; 84             } 85              86         } 87     } 88     else 89     { 90         //Ò»°ãÇé¿ö  91         dir = (dir+1) % 4; 92         for(int i = 0; i < 4; ++i) 93         { 94             int nx = x + dx[(dir-i+4)%4]; 95             int ny = y + dy[(dir-i+4)%4]; 96             if(nx >= 0 && nx < w && ny >= 0 && ny < h && maze[ny][nx] != ‘#‘) 97             { 98                 rightOrder(nx, ny , sum+1, (dir-i+4)%4); 99                 break;100             }        101         }    102     }103     104 } 105 106 int shortPath()107 {108     queue<P> que; 109     dist[startY][startX] = 1;110     que.push(P(startX, startY));111     while(que.size())112     {113         P temp = que.front();114         que.pop();115         if(temp.first == endX && temp.second == endY)116             break;117         for(int i = 0; i < 4; ++i)118         {119             int nx = temp.first + spDirX[i];120             int ny = temp.second + spDirY[i];121             if(nx >= 0 && ny >= 0 && nx < w && ny < h && dist[ny][nx] == INF && maze[ny][nx] != ‘#‘)122             {123                 que.push(P(nx, ny));124                 dist[ny][nx] = dist[temp.second][temp.first] + 1;125             }126         }        127     }128     sp = dist[endY][endX];129 }130 131 132 int main()133 {134     cin >> n;135     for(int i = 0; i < n; ++i)136     {137         cin >> w >> h;138         for(int j = 0; j < h; ++j)139         {140             for(int k = 0; k < w; ++k)141             {142                 cin >> maze[j][k];143                 dist[j][k] = INF;144                 if(maze[j][k] == ‘S‘)145                 {146                     startX = k;147                     startY = j;148                 }149                 if(maze[j][k] == ‘E‘)150                 {151                     endX = k;152                     endY = j;153                 }    154             }155         }156         leftOrder(startX, startY, 1, 0);157         rightOrder(startX, startY, 1, 0);158         shortPath();    159         cout << lo << " " << ro << " " << sp << endl;    160     }161     return 0;162 }