問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3083思路:
對于求最短路徑，BFS即可解決，沒有什么難度
該題的難點在于如何求沿左、沿右走的問題
剛開始，完全不知道這是什么意思，無奈只能在網(wǎng)上看代碼，總結(jié)如下:
沿左策略的一般次序: left, up, right, down
沿右策略的一般次序: right, up, left, down
求解的關(guān)鍵是如何根據(jù)前一個方向以及一般次序來決定目前訪問上下左右四個方向的順序，例如:
對于沿左前進策略，如果前一個方向是right，那么訪問次序是up, right, down, left(與前一個方向相反的方向總是放在最后)
代碼:
1 #define MAX_LEN 42
2 #define QUEUE_LEN 1600
3 #define is_valid(x, y) (x>=0 && x<row && y>=0 && y<col)
4 char maze[MAX_LEN][MAX_LEN];
5 int visited[MAX_LEN][MAX_LEN];
6 int row, col;
7 int start_x, start_y;
8 /* left, up, right, down */
9 const int dx[] = {0, -1, 0, 1};
10 const int dy[] = {-1, 0, 1, 0};
11 /* right, up, left, down */
12 const int dx_right[] = {0, -1, 0, 1};
13 const int dy_right[] = {1, 0, -1, 0};
14 int lcount, rcount;
15 int head, tail;
16 struct EACH {
17 int x, y;
18 int mv;
19 } queue[QUEUE_LEN];
20
21
22 void
23 init()
24 {
25 int i;
26 char *p;
27 memset(visited, 0, sizeof(visited));
28 head = -1;
29 tail = 0;
30 lcount = rcount = 0;
31 scanf("%d %d", &col, &row);
32 for(i=0; i<row; i++) {
33 scanf("%s", maze[i]);
34 if((p=strchr(maze[i], 'S')) != NULL) {
35 start_x = i;
36 start_y = p-maze[i];
37 }
38 }
39 }
40
41 /*
42 * dir: previous direction
43 * switch(dir):
44 * case(right): up right down left (order)
45 * case(up): left up right down
46 * case(left): down left up right
47 * case(down): right down left up
48 */
49 void
50 dfs_left(int x, int y, int dir)
51 {
52 int i, tx, ty;
53 ++lcount;
54 if(maze[x][y] == 'E') {
55 return;
56 }
57 dir = (dir+3)%4;
58 for(i=0; i<4; i++) {
59 tx = x + dx[(dir+i)%4];
60 ty = y + dy[(dir+i)%4];
61 if(is_valid(tx, ty) && maze[tx][ty]!='#') {
62 dfs_left(tx, ty, (dir+i)%4);
63 break;
64 }
65 }
66 }
67
68 void
69 dfs_right(int x, int y, int dir)
70 {
71 int i, tx, ty;
72 ++rcount;
73 if(maze[x][y] == 'E')
74 return;
75 dir = (dir+3)%4;
76 for(i=0; i<4; i++) {
77 tx = x + dx_right[(dir+i)%4];
78 ty = y + dy_right[(dir+i)%4];
79 if(is_valid(tx, ty) && maze[tx][ty]!='#') {
80 dfs_right(tx, ty, (dir+i)%4);
81 break;
82 }
83 }
84 }
85
86 int
87 bfs()
88 {
89 int i, cx, cy, tx, ty, cmv;
90 memset(visited, 0, sizeof(visited));
91 queue[tail].x = start_x;
92 queue[tail].y = start_y;
93 queue[tail].mv = 1;
94 visited[start_x][start_y] = 1;
95 while(head < tail) {
96 ++head;
97 cx = queue[head].x;
98 cy = queue[head].y;
99 cmv = queue[head].mv;
100 if(maze[cx][cy] == 'E')
101 return cmv;
102 for(i=0; i<4; i++) {
103 tx = cx + dx[i];
104 ty = cy + dy[i];
105 if(is_valid(tx, ty) && !visited[tx][ty] && maze[tx][ty]!='#') {
106 ++tail;
107 queue[tail].x = tx;
108 queue[tail].y = ty;
109 queue[tail].mv = cmv+1;
110 visited[tx][ty] = 1;
111 }
112 }
113 }
114 }