问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1101思路:
宽度优先搜索
要点: 每次扩展的时候，在各个方向(上下左右)，不是简单地只扩展一格，而是“直线延伸”式的扩展
另外，由于允许路径超出board范围，所以在上下左右各多放置一栏空白
由于使用C来写，所以队列就简单地用数组模拟，一般情况下还是可行的，不过有时可能比较浪费空间，又有时可能会分配数组大小不够而出现RE
队列的每个Element是一个State结构，其中包含了点坐标及到达该点的最小segments
其实，虽然AC了，还是一直有个疑问，在找到目的点的时候，我们得到一个segments个数，而且就直接将其作为问题的解，那会不会在另外一个方向存在另一条路径到达这个目的点，而且其segments个数更小，只是该条路径在队列中尚未被访问到？这也是当初我将vstd_drt数组设置成某点是否被访问过及其被访问的方向的初衷
1 #define SIZE_MAX 77 /* 75+2 */
2 #define UP 1
3 #define DOWN 2
4 #define LEFT 4
5 #define RIGHT 8
6 char board[SIZE_MAX][SIZE_MAX];
7 int vstd_drt[SIZE_MAX][SIZE_MAX];
8 int width, height;
9 int start_x, start_y, end_x, end_y;
10 struct State {
11 int x;
12 int y;
13 int min;
14 };
15 struct State queue[SIZE_MAX*SIZE_MAX];
16 int head, tail;
17 const int dx[] = {-1, 1, 0, 0};
18 const int dy[] = {0, 0, -1, 1};
19
20 int
21 is_valid(int x, int y)
22 {
23 return (x>=0 && x<=height+1 && y>=0 && y<=width+1);
24 }
25
26 #define ADD(i, j, min, drt) ++tail; \
27 queue[tail].x = i; \
28 queue[tail].y = j; \
29 queue[tail].min = min; \
30 vstd_drt[i][j] = drt;
31
32 void
33 push_queue(int x, int y, int drt, int min)
34 {
35 int i, j;
36 switch(drt) {
37 case UP:
38 j = y;
39 for(i=x; i>=0; i--) {
40 if(board[i][j]=='X')
41 break;
42 if(!vstd_drt[i][j]) {
43 ADD(i, j, min, drt);
44 }
45 }
46 break;
47 case DOWN:
48 j = y;
49 for(i=x; i<=height+1; i++) {
50 if(board[i][j]=='X')
51 break;
52 if(!vstd_drt[i][j]) {
53 ADD(i, j, min, drt);
54 }
55 }
56 break;
57 case LEFT:
58 i = x;
59 for(j=y; j>=0; j--) {
60 if(board[i][j]=='X')
61 break;
62 if(!vstd_drt[i][j]) {
63 ADD(i, j, min, drt);
64 }
65 }
66 break;
67 case RIGHT:
68 i = x;
69 for(j=y; j<=width+1; j++) {
70 if(board[i][j]=='X')
71 break;
72 if(!vstd_drt[i][j]) {
73 ADD(i, j, min, drt);
74 }
75 }
76 break;
77 }
78 }
79
80 int
81 bfs()
82 {
83 int i, j, cur_x, cur_y, cur_min, nx, ny;
84 for(i=0; i<4; i++) {
85 nx = start_x + dx[i];
86 ny = start_y + dy[i];
87 if(is_valid(nx, ny) && board[nx][ny]==' ' && !vstd_drt[nx][ny])
88 push_queue(nx, ny, 1<<i, 1);
89 }
90 while(head<tail) {
91 ++head;
92 cur_x = queue[head].x;
93 cur_y = queue[head].y;
94 cur_min = queue[head].min;
95 if(cur_x==end_x && cur_y==end_y)
96 return cur_min;
97 for(i=0; i<4; i++) {
98 nx = cur_x + dx[i];
99 ny = cur_y + dy[i];
100 if(is_valid(nx, ny) && board[nx][ny]==' ' && !vstd_drt[nx][ny])
101 push_queue(nx, ny, 1<<i, cur_min+1);
102 }
103 }
104 return -1;
105 }