題目鏈接：http://acm.pku.edu.cn/JudgeOnline/problem?id=3083
題目描述：求最短路，求沿特定方向走迷宮的步數
所用算法：最短路用bfs求，特定方向走迷宮直接用while計數（這里寫的比較繁瑣，要細心，本來看題目分類是在dfs里面的，以為這要用dfs，細想想不用，而求迷宮最短路徑，bfs應該是首選了）
提交情況：1次wa(忘了加<stdio.h>頭文件)，一次re（在隊列數組開的太小）
心得體會：好久沒有做迷宮題了，今天做了一道，各種別扭。題目不難，仔細讀題就可以了。求最短路實際上就是個模板，和2251一樣。中間寫完還出現段錯誤的情況，是用gets/fgets（）讀map造成的，然后我就改成了逐行讀字符串。題目數據并不大，因為暴搜也0ms就過了，但很納悶為什么這個數據規模隊列開成1000就re，其實也差不多了，40＊40無非就1600種情況而已，下次開數組時不能想當然，一定要走腦子后再開。
1 #include<iostream>
2 #include<stdio.h>
3 using namespace std;
4
5 #define EAST 1
6 #define WEST 2
7 #define SOUTH 3
8 #define NORTH 4
9
10 char map[100][100];
11 struct pos
12 {
13 int x;
14 int y;
15 int pre;
16 };
17
18 int w;
19 int h;
20
21 pos queue[20000];
22
23 const int d1[]={1,-1,0,0};
24 const int d2[]={0,0,1,-1};
25 int bfs(int x,int y)
26 {
27 int head=0;
28 int tail=0;
29 queue[tail].x=x;
30 queue[tail].y=y;
31 queue[tail].pre=-1;
32 tail++;
33 pos temp;
34 pos next;
35 int step=0;
36 while(head!=tail)
37 {
38 temp.x=queue[head].x;
39 temp.y=queue[head].y;
40 head++;
41 for(int i=0;i<4;i++)
42 {
43 next.x=temp.x+d1[i];
44 next.y=temp.y+d2[i];
45 next.pre=head-1;
46
47 if(next.x>=0&&next.x<h&&next.y>=0&&next.y<w&&map[next.x][next.y]=='E')
48 {
49 goto END;
50 }
51
52 if(next.x>=0&&next.x<h&&next.y>=0&&next.y<w&&map[next.x][next.y]!='#')
53 {
54 queue[tail].x=next.x;
55 queue[tail].y=next.y;
56 queue[tail].pre=next.pre;
57 tail++;
58 map[next.x][next.y]='#';
59 }
60 }
61 }
62 return -1;
63 END:
64 while(next.pre!=-1)
65 {
66 next.pre=queue[next.pre].pre;
67 step++;
68 }
69 return step;
70 }
71
72 int mleft(int x,int y,int direct)
73 {
74 int l=0;
75 while(map[x][y]!='E')
76 {
77 switch(direct)
78 {
79 case EAST:
80 if(x-1>=0&&map[x-1][y]!='#')
81 {
82 x=x-1;
83 direct=NORTH;
84 }
85 else if(y+1<w&&map[x][y+1]!='#')
86 {
87 y=y+1;
88 direct=EAST;
89 }
90 else if(x+1<h&&map[x+1][y]!='#')
91 {
92 x=x+1;
93 direct=SOUTH;
94 }
95 else if(y-1>=0&&map[x][y-1]!='#')
96 {
97 y=y-1;
98 direct=WEST;
99 }
100 l++;
101 break;
102 case SOUTH:
103 if(y+1<w&&map[x][y+1]!='#')
104 {
105 y=y+1;
106 direct=EAST;
107 }
108 else if(x+1<h&&map[x+1][y]!='#')
109 {
110 x=x+1;
111 direct=SOUTH;
112 }
113 else if(y-1>=0&&map[x][y-1]!='#')
114 {
115 y=y-1;
116 direct=WEST;
117 }
118 else if(x-1>=0&&map[x-1][y]!='#')
119 {
120 x=x-1;
121 direct=NORTH;
122 }
123 l++;
124 break;
125
126 case WEST:
127 if(x+1<h&&map[x+1][y]!='#')
128 {
129 x=x+1;
130 direct=SOUTH;
131 }
132 else if(y-1>=0&&map[x][y-1]!='#')
133 {
134 y=y-1;
135 direct=WEST;
136 }
137 else if(x-1>=0&&map[x-1][y]!='#')
138 {
139 x=x-1;
140 direct=NORTH;
141 }
142 else if(y+1<w&&map[x][y+1]!='#')
143 {
144 y=y+1;
145 direct=EAST;
146 }
147 l++;
148 break;
149 case NORTH:
150 if(y-1>=0&&map[x][y-1]!='#')
151 {
152 y=y-1;
153 direct=WEST;
154 }
155 else if(x-1>=0&&map[x-1][y]!='#')
156 {
157 x=x-1;
158 direct=NORTH;
159 }
160 else if(y+1<w&&map[x][y+1]!='#')
161 {
162 y=y+1;
163 direct=EAST;
164 }
165 else if(x+1<h&&map[x+1][y]!='#')
166 {
167 x=x+1;
168 direct=SOUTH;
169 }
170 l++;
171 break;
172 }
173 }
174 return l;
175 }
176
177
178 int mright(int x,int y,int direct)
179 {
180 int r=0;
181 while(map[x][y]!='E')
182 {
183 switch(direct)
184 {
185 case EAST:
186 if(x+1<h&&map[x+1][y]!='#')
187 {
188 x=x+1;
189 direct=SOUTH;
190 }
191 else if(y+1<w&&map[x][y+1]!='#')
192 {
193 y=y+1;
194 direct=EAST;
195 }
196 else if(x-1>=0&&map[x-1][y]!='#')
197 {
198 x=x-1;
199 direct=NORTH;
200 }
201 else if(y-1>=0&&map[x][y-1]!='#')
202 {
203 y=y-1;
204 direct=WEST;
205 }
206 r++;
207 break;
208 case NORTH:
209 if(y+1<w&&map[x][y+1]!='#')
210 {
211 y=y+1;
212 direct=EAST;
213 }
214 else if(x-1>=0&&map[x-1][y]!='#')
215 {
216 x=x-1;
217 direct=NORTH;
218 }
219 else if(y-1>=0&&map[x][y-1]!='#')
220 {
221 y=y-1;
222 direct=WEST;
223 }
224 else if(x+1<h&&map[x+1][y]!='#')
225 {
226 x=x+1;
227 direct=SOUTH;
228 }
229 r++;
230 break;
231 case WEST:
232 if(x-1>=0&&map[x-1][y]!='#')
233 {
234 x=x-1;
235 direct=NORTH;
236 }
237 else if(y-1>=0&&map[x][y-1]!='#')
238 {
239 y=y-1;
240 direct=WEST;
241 }
242 else if(x+1<h&&map[x+1][y]!='#')
243 {
244 x=x+1;
245 direct=SOUTH;
246 }
247 else if(y+1<w&&map[x][y+1]!='#')
248 {
249 y=y+1;
250 direct=EAST;
251 }
252 r++;
253 break;
254 case SOUTH:
255 if(y-1>=0&&map[x][y-1]!='#')
256 {
257 y=y-1;
258 direct=WEST;
259 }
260 else if(x+1<h&&map[x+1][y]!='#')
261 {
262 x=x+1;
263 direct=SOUTH;
264 }
265 else if(y+1<w&&map[x][y+1]!='#')
266 {
267 y=y+1;
268 direct=EAST;
269 }
270 else if(x-1>=0&&map[x-1][y]!='#')
271 {
272 x=x-1;
273 direct=NORTH;
274 }
275 r++;
276 break;
277 }
278 }
279 return r;
280 }
281
282
283 int main()
284 {
285 //freopen("data.in","r",stdin);
286 int testcase;
287 cin>>testcase;
288 while(testcase--)
289 {
290 int lv;
291 int rv;
292 int mv;
293 cin>>w>>h;
294 string str;
295 int x,y,direct;
296 for(int i=0;i<h;i++)
297 {
298 cin>>str;
299 const char *p=str.c_str();
300 for(int j=0;j<w;j++)
301 {
302 map[i][j]=p[j];
303 }
304 }
305 for(int i=0;i<h;i++)
306 {
307 for(int j=0;j<w;j++)
308 {
309 if(map[i][j]=='S')
310 {
311 x=i;
312 y=j;
313 map[i][j]='#';
314 }
315 }
316 }
317
318 if(x==0)
319 direct=SOUTH;
320 else if(x==h-1)
321 direct=NORTH;
322 else if(y==0)
323 direct=EAST;
324 else if(y==w-1)
325 direct=WEST;
326
327 lv=mleft(x,y,direct)+1;
328 rv=mright(x,y,direct)+1;
329 mv=bfs(x,y)+1;
330 printf("%d %d %d\\n",lv,rv,mv);
331 }
332 }