問題:
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 }