1 #include<cstdio>  2 #include<cstring>  3 #include<queue>  4   5 using namespace std;  6 typedef pair<int,int>P;  7 const int dx[4]={1,0,-1,0};  8 const int dy[4]={0,1,0,-1};  9 const int INF=1e9; 10 int sx,sy,ex,ey,n,m; 11 char a[50][50]; 12 int d[50][50]; 13  14 bool pd(int x,int y) 15 { 16     if (x>=0 && x<n && y>=0 && y<m && a[x][y]!=‘#‘) return true; 17     return false; 18 } 19  20 int dfs(int x,int y,int xx,int yy,char d) 21 { 22     if (x==xx && y==yy) return 1; 23     if (d==‘U‘) 24     { 25         if (pd(x-1,y)) return dfs(x-1,y,xx,yy,‘L‘)+1; 26         else if (pd(x,y-1)) return dfs(x,y-1,xx,yy,‘U‘)+1; 27         else if (pd(x+1,y)) return dfs(x+1,y,xx,yy,‘R‘)+1; 28         else if (pd(x,y+1)) return dfs(x,y+1,xx,yy,‘D‘)+1; 29     } 30     else if (d==‘L‘) 31     { 32         if (pd(x,y+1)) return dfs(x,y+1,xx,yy,‘D‘)+1; 33         else if (pd(x-1,y)) return dfs(x-1,y,xx,yy,‘L‘)+1; 34         else if (pd(x,y-1)) return dfs(x,y-1,xx,yy,‘U‘)+1; 35         else if (pd(x+1,y)) return dfs(x+1,y,xx,yy,‘R‘)+1; 36     } 37     else if (d==‘D‘) 38     { 39         if (pd(x+1,y)) return dfs(x+1,y,xx,yy,‘R‘)+1; 40         else if (pd(x,y+1)) return dfs(x,y+1,xx,yy,‘D‘)+1; 41         else if (pd(x-1,y)) return dfs(x-1,y,xx,yy,‘L‘)+1; 42         else if (pd(x,y-1)) return dfs(x,y-1,xx,yy,‘U‘)+1; 43     } 44     else if (d==‘R‘) 45     { 46         if (pd(x,y-1)) return dfs(x,y-1,xx,yy,‘U‘)+1; 47         else if (pd(x+1,y)) return dfs(x+1,y,xx,yy,‘R‘)+1; 48         else if (pd(x,y+1)) return dfs(x,y+1,xx,yy,‘D‘)+1; 49         else if (pd(x-1,y)) return dfs(x-1,y,xx,yy,‘L‘)+1; 50     } 51 } 52  53 int bfs(int sx,int sy,int ex,int ey) 54 { 55     int v[50][50]; 56     for (int i=0;i<50;i++) 57         for (int j=0;j<50;j++) d[i][j]=INF; 58  59     queue<P> que; 60     que.push(P(sx,sy)); 61     d[sx][sy]=1; 62     while (que.size()) 63     { 64         P p=que.front(); 65         que.pop(); 66         if (p.first==ex && p.second==ey) break; 67         for (int i=0;i<4;i++) 68         { 69             int nx=p.first+dx[i]; 70             int ny=p.second+dy[i]; 71             if (pd(nx,ny) && d[nx][ny]==INF) 72             { 73                 que.push(P(nx,ny)); 74                 d[nx][ny]=d[p.first][p.second]+1; 75             } 76        } 77     } 78     return d[ex][ey]; 79 } 80 int main() 81 { 82     int tot; 83     scanf("%d",&tot); 84     for(int t=1;t<=tot;t++) 85     { 86         scanf("%d%d",&m,&n); 87         for (int i=0;i<n;i++) 88         { 89             scanf("%s",a[i]); 90             for(int j=0;j<m;j++) 91             { 92                 if (a[i][j]==‘S‘) 93                 { 94                     sx=i; 95                     sy=j; 96                 }else 97                 if (a[i][j]==‘E‘) 98                 { 99                     ex=i;100                     ey=j;101                 }102             }103         }104       //  printf("%d %d\n",ex,ey);105         int ans2=dfs(sx,sy,ex,ey,‘U‘);106         int ans1=dfs(ex,ey,sx,sy,‘U‘);107         int ans3=bfs(sx,sy,ex,ey);108         printf("%d %d %d\n",ans1,ans2,ans3);109     }110     return 0;111 }