问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3083思路:
对于求最短路径，BFS即可解决，没有什么难度
该题的难点在于如何求沿左、沿右走的问题
刚开始，完全不知道这是什么意思，无奈只能在网上看代码，总结如下:
沿左策略的一般次序: left, up, right, down
沿右策略的一般次序: right, up, left, down
求解的关键是如何根据前一个方向以及一般次序来决定目前访问上下左右四个方向的顺序，例如:
对于沿左前进策略，如果前一个方向是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 }