1 //3083 Accepted 416K 16MS G++ 5141B PKU Children of the Candy Corn
2
3 //深搜 + 广搜
4
5 #include <stdio.h>
6 #include <stdlib.h>
7 #include <string.h>
8
9 const int size = 50 ;
10 char data[size][size] ;
11 int flag[size][size] ;
12
13 struct QUE
14 {
15 int r ;
16 int c ;
17 int step ;
18 };
19 struct QUE que[100000] ;
20 int head, tail ;
21
22 int ldir[5][3] ; int rdir[5][3] ;//左右方向
23 int udir[5][3] ; int ddir[5][3] ;//上下方向
24
25 int innum ;
26 int inrow, incol ;
27
28 int snr, snc ;
29 int enr, enc ;
30
31 int rval, lval, minval ; bool OK ;
32
33 void input()
34 {
35 scanf( "%d %d", &incol, &inrow ) ;
36
37 for( int i=1; i<=inrow; i++ )
38 {
39 scanf( "%s", data[i]+1 ) ; //printf( "%s\n", data[i]+1 ) ;
40 }
41
42 for( int r=1; r<=inrow; r++ )
43 {
44 for( int c=1; c<=incol; c++ )
45 {
46 if( 'S' == data[r][c] ) { snr = r , snc = c ; }
47 if( 'E' == data[r][c] ) { enr = r , enc = c ; }
48 }
49 }
50 }
51
52 bool fin( int r, int c )
53 {
54 if( r>=1 && r<=inrow && c>=1 && c<=incol ) return true ;
55 else return false ;
56 }
57
58 void DFS_left( int sr, int sc, int d, int step )
59 {
60 if( OK ) return ;
61 if( 'E' == data[sr][sc] )
62 {
63 lval = step ; OK = true ; return ;
64 }
65
66 int nextr = sr+ldir[d][0] ; int nextc = sc+ldir[d][1] ; int curd = ldir[d][2] ;
67 if( fin(nextr, nextc) && ('.'==data[nextr][nextc]||'E'==data[nextr][nextc] ) )
68 DFS_left( nextr, nextc, curd, step+1 ) ;
69
70 if( OK ) return ;
71
72 nextr = sr+udir[d][0] ; nextc = sc+udir[d][1] ; curd = d ;
73 if( fin(nextr, nextc) && ('.'==data[nextr][nextc]||'E'==data[nextr][nextc] ) )
74 DFS_left( nextr, nextc, curd, step+1 ) ;
75
76 if( OK ) return ;
77
78 nextr = sr+rdir[d][0] ; nextc = sc+rdir[d][1] ; curd = rdir[d][2] ;
79 if( fin(nextr, nextc) && ('.'==data[nextr][nextc]||'E'==data[nextr][nextc] ) )
80 DFS_left( nextr, nextc, curd, step+1 ) ;
81
82 if( OK ) return ;
83
84 nextr = sr+ddir[d][0] ; nextc = sc+ddir[d][1] ; curd = 5-d ;
85 DFS_left( nextr, nextc, curd, step+1 ) ;
86 }
87
88 void DFS_right( int sr, int sc, int d, int step )
89 {
90 if( OK ) return ;
91 if( 'E' == data[sr][sc] )
92 {
93 rval = step ; OK = true ; return ;
94 }
95
96 int nextr = sr+rdir[d][0] ; int nextc = sc+rdir[d][1] ; int curd = rdir[d][2] ;
97 if( fin(nextr, nextc) && ('.'==data[nextr][nextc]||'E'==data[nextr][nextc] ) )
98 DFS_right( nextr, nextc, curd, step+1 ) ;
99
100 if( OK ) return ;
101
102 nextr = sr+udir[d][0] ; nextc = sc+udir[d][1] ; curd = d ;
103 if( fin(nextr, nextc) && ('.'==data[nextr][nextc]||'E'==data[nextr][nextc] ) )
104 DFS_right( nextr, nextc, curd, step+1 ) ;
105
106 if( OK ) return ;
107
108 nextr = sr+ldir[d][0] ; nextc = sc+ldir[d][1] ; curd = ldir[d][2] ;
109 if( fin(nextr, nextc) && ('.'==data[nextr][nextc]||'E'==data[nextr][nextc] ) )
110 DFS_right( nextr, nextc, curd, step+1 ) ;
111
112 if( OK ) return ;
113
114 nextr = sr+ddir[d][0] ; nextc = sc+ddir[d][1] ; curd = 5-d ;
115 DFS_right( nextr, nextc, curd, step+1 ) ;
116 }
117
118 void left()
119 {
120 int direct ;
121 if( 1 == snr ) direct = 4 ;
122 if( 1 == snc ) direct = 3 ;
123 if( inrow == snr ) direct = 1 ;
124 if( incol == snc ) direct = 2 ;
125
126 OK = false ;
127 DFS_left( snr, snc, direct, 1 ) ;
128 }
129 void right()
130 {
131 int direct ;
132 if( 1 == snr ) direct = 4 ;
133 if( 1 == snc ) direct = 3 ;
134 if( inrow == snr ) direct = 1 ;
135 if( incol == snc ) direct = 2 ;
136
137 OK = false ;
138 DFS_right( snr, snc, direct, 1 ) ;
139 }
140 void init()
141 {
142 ldir[1][0] = 0 ; ldir[1][1] = -1 ; ldir[1][2] = 2 ;//1
143 ldir[2][0] = 1 ; ldir[2][1] = 0 ; ldir[2][2] = 4 ;
144 ldir[3][0] = -1 ; ldir[3][1] = 0 ; ldir[3][2] = 1 ;
145 ldir[4][0] = 0 ; ldir[4][1] = 1 ; ldir[4][2] = 3 ;
146
147 rdir[1][0] = 0 ; rdir[1][1] = 1 ; rdir[1][2] = 3 ;//1
148 rdir[2][0] = -1 ; rdir[2][1] = 0 ; rdir[2][2] = 1 ;
149 rdir[3][0] = 1 ; rdir[3][1] = 0 ; rdir[3][2] = 4 ;
150 rdir[4][0] = 0 ; rdir[4][1] = -1 ; rdir[4][2] = 2 ;
151
152 udir[1][0] = -1 ; udir[1][1] = 0 ; udir[1][2] = 3 ;//1
153 udir[2][0] = 0 ; udir[2][1] = -1 ; udir[2][2] = 1 ;
154 udir[3][0] = 0 ; udir[3][1] = 1 ; udir[3][2] = 4 ;
155 udir[4][0] = 1 ; udir[4][1] = 0 ; udir[4][2] = 2 ;
156
157 ddir[1][0] = 1 ; ddir[1][1] = 0 ; ddir[1][2] = 3 ;//1
158 ddir[2][0] = 0 ; ddir[2][1] = 1 ; ddir[2][2] = 1 ;
159 ddir[3][0] = 0 ; ddir[3][1] = -1 ; ddir[3][2] = 4 ;
160 ddir[4][0] = -1 ; ddir[4][1] = 0 ; ddir[4][2] = 2 ;
161 }
162
163 void BFS()
164 {
165 memset( flag, 0, sizeof(flag) ) ;
166 head = tail = 0 ; int curr ; int curc ;
167 que[tail].r = snr ; que[tail].c = snc ; que[tail++].step = 1 ; flag[snr][snc] = 1 ;
168
169 while( head < tail )
170 {
171 curr = que[head].r ; curc = que[head].c ;
172
173 if( 'E' == data[curr][curc] ) { minval = que[head].step ; return ; }
174
175 for( int i=1; i<=4; i++ ) {
176 curr = que[head].r+rdir[i][0] ; curc = que[head].c+rdir[i][1] ;
177 if( fin(curr, curc) && 0==flag[curr][curc]&&'.'==data[curr][curc]||'E'==data[curr][curc] )
178 {
179 flag[curr][curc] = 1 ; que[tail].r = curr ; que[tail].c = curc ; que[tail++].step = que[head].step+1 ;
180 }
181 }
182 head++ ;
183 }
184 }
185
186 void process()
187 {
188 init() ;
189
190 left() ;
191
192 right() ;
193
194 BFS() ;
195
196 printf( "%d %d %d\n", lval, rval, minval ) ;
197 }
198
199 int main()
200 {
201 //freopen( "in.txt", "r", stdin ) ;
202
203 while( scanf( "%d", &innum ) != EOF )
204 {
205 for( int ct=1; ct<=innum; ct++ )
206 {
207 input() ;
208
209 process() ;
210
211 //output() ;
212 }
213 }
214
215 return 0 ;
216 }