1 #include<iostream>  2 #include<stdio.h>  3 #include<cstring>  4 #include<iomanip>  5 #include<queue>  6 #include<algorithm>  7 using namespace std;  8 struct node  9 { 10     int w; 11     int e; 12     int step; 13 }; 14 int n,m; 15 int vist[50][50]; 16 int r[4][2]= {{0,-1},{1,0},{0,1},{-1,0}}; 17 int l[4][2]= {{0,1},{1,0},{0,-1},{-1,0}}; 18 int dir[4][2]={{0,1},{-1,0},{1,0},{0,-1}}; 19 char map[50][50]; 20 int sx,sy,ex,ey,ans; 21 int dfs1(int x,int y,int step) 22 { 23     if(x==ex&&y==ey) 24         return step+1; 25     if(x<0||x>=n||y<0||y>=m||map[x][y]==‘#‘) 26         return 0; 27     ans=(ans+3)%4; 28     int temp=0; 29     while(1) 30     { 31         temp=dfs1(x+l[ans][0],y+l[ans][1],step+1); 32         if(temp!=0) 33             break; 34         ans=(ans+1)%4; 35     } 36     return temp; 37 } 38 int dfs2(int x,int y,int step) 39 { 40     if(x==ex&&y==ey) 41         return step+1; 42     if(x<0||x>=n||y<0||y>=m||map[x][y]==‘#‘) 43         return 0; 44     ans=(ans+3)%4; 45     int temp=0; 46     while(1) 47     { 48         temp=dfs2(x+r[ans][0],y+r[ans][1],step+1); 49         if(temp!=0) 50             break; 51         ans=(ans+1)%4; 52     } 53     return temp; 54 } 55 int bfs() 56 { 57     memset(vist,0,sizeof(vist)); 58     int i,x,y; 59     struct node p; 60     queue<struct node>Q; 61     p.w=sx; 62     p.e=sy; 63     p.step=1; 64     Q.push(p); 65     vist[sx][sy]=1; 66     while(!Q.empty()) 67     { 68         p=Q.front(); 69         Q.pop(); 70         if(p.w==ex&&p.e==ey) 71             return p.step; 72         for(i=0;i<4;i++) 73         { 74             x=p.w+dir[i][0]; 75             y=p.e+dir[i][1]; 76             if(x>=0&&x<n&&y>=0&&y<m&&map[x][y]!=‘#‘&&vist[x][y]==0) 77             { 78                 vist[x][y]=1; 79                 struct node t; 80                 t.w=x; 81                 t.e=y; 82                 t.step=p.step+1; 83                 Q.push(t); 84             } 85         } 86     } 87 } 88 int main() 89 { 90     int T; 91     scanf("%d",&T); 92     while(T--) 93     { 94         scanf("%d%d",&m,&n); 95         getchar(); 96         for(int i=0; i<n; i++) 97         { 98             for(int j=0; j<m; j++) 99             {100                 scanf("%c",&map[i][j]);101                 if(map[i][j]==‘S‘)102                 {103                     sx=i;104                     sy=j;105                 }106                 if(map[i][j]==‘E‘)107                 {108                     ex=i;109                     ey=j;110                 }111             }112             getchar();113         }114         ans=0;115         printf("%d ",dfs1(sx,sy,0));116         ans=0;117         printf("%d ",dfs2(sx,sy,0));118         printf("%d\n",bfs());119     }120     return 0;121 }