問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2251思路:
三維的迷宮
其實，該題是典型的BFS
不過由于二維迷宮的影響以及網上題目分類的誤導，開始直接DFS，結果TLE
值得小慶祝一番的是: 這是AC的第50題(*^__^*) 嘻嘻……，繼續加油
代碼:
TLE的DFS
1 void
2 dfs(int sl, int sr, int sc, int m)
3 {
4 if(m >= min) /* pruning */
5 return;
6 if(sl==end_l && sr==end_r && sc==end_c) {
7 min = m;
8 return;
9 }
10 int i, tl, tr, tc;
11 for(i=0; i<6; i++) {
12 tl = sl + dl[i];
13 tr = sr + dr[i];
14 tc = sc + dc[i];
15 if(is_valid(tl, tr, tc) && !visited[tl][tr][tc] && maze[tl][tr][tc]!='#') {
16 visited[tl][tr][tc] = 1;
17 dfs(tl, tr, tc, m+1);
18 visited[tl][tr][tc] = 0;
19 }
20 }
21 }
AC的BFS
1 #define MAX_SIZE 31
2 #define QUEUE_SIZE 100000
3 #define is_valid(l, r, c) (l>=0 && l<level && r>=0 && r<row && c>=0 && c<column)
4 char maze[MAX_SIZE][MAX_SIZE][MAX_SIZE];
5 int visited[MAX_SIZE][MAX_SIZE][MAX_SIZE];
6 int level, row, column;
7 int begin_l, begin_r, begin_c;
8 int end_l, end_r, end_c;
9 /* direction: north, south, west, east, up, down */
10 const int dl[] = {0, 0, 0, 0, -1, 1};
11 const int dr[] = {-1, 1, 0, 0, 0, 0};
12 const int dc[] = {0, 0, -1, 1, 0, 0};
13 struct EACH {
14 int l, r, c;
15 int mins;
16 } queue[QUEUE_SIZE];
17 int head, tail;
18
19
20 void
21 init()
22 {
23 int i, j;
24 char *p;
25 memset(visited, 0, sizeof(visited));
26 memset(queue, 0, sizeof(queue));
27 head = -1;
28 tail = 0;
29 for(i=0; i<level; i++) {
30 for(j=0; j<row; j++) {
31 scanf("%s", maze[i][j]);
32 if((p=strchr(maze[i][j], 'S')) != NULL) {
33 begin_l = i;
34 begin_r = j;
35 begin_c = p-maze[i][j];
36 }
37 if((p=strchr(maze[i][j], 'E')) != NULL) {
38 end_l = i;
39 end_r = j;
40 end_c = p-maze[i][j];
41 }
42 }
43 getchar();
44 }
45 }
46
47 int
48 bfs()
49 {
50 int i, tl, tr, tc, cl, cr, cc, cm;
51 queue[tail].l = begin_l;
52 queue[tail].r = begin_r;
53 queue[tail].c = begin_c;
54 queue[tail].mins = 0;
55 visited[begin_l][begin_r][begin_c] = 1;
56 while(head < tail) {
57 ++head;
58 cl = queue[head].l;
59 cr = queue[head].r;
60 cc = queue[head].c;
61 cm = queue[head].mins;
62 if(cl==end_l && cr==end_r && cc==end_c)
63 return cm;
64 for(i=0; i<6; i++) {
65 tl = cl + dl[i];
66 tr = cr + dr[i];
67 tc = cc + dc[i];
68 if(is_valid(tl, tr, tc) && !visited[tl][tr][tc] && maze[tl][tr][tc]!='#') {
69 visited[tl][tr][tc] = 1;
70 ++tail;
71 queue[tail].l = tl;
72 queue[tail].r = tr;
73 queue[tail].c = tc;
74 queue[tail].mins = cm+1;
75 }
76 }
77 }
78 return -1;
79 }