bfs的好題目！
開始想到用優先隊列，無情的還是過了， 只不過時間用了2000ms多，差點就掛了~杯具的優先
后來一想，其實可以直接bfs, 有情的是意料之外的沒有出現TE，而是AC，徹底無語的是只用了500ms多！?。?！
大呼優先之哀哉……
至于bfs的做法如下：
1，開始點進棧
2，開始點能直接到達(不花時間的)的所有的點進棧
3，分兩步
3.1 開始點不能直接到達（要時間）的點進棧
3.2 將這個點能直接到達(不花時間的)的所有的點進棧
3.3 跳轉到3
4 跳轉到1
注：開始點為當前出棧的第一個點
不明白這個過程的可以看代碼（雖然代碼有點……，還可以進一步簡化， 以后不能老想著優先了，誰優先誰杯具，當然不是說我們的廣大女同胞……）
1 #include <iostream>
2 #include <queue>
3 using namespace std;
4 struct node
5 {
6 int x, y, time;
7 /*friend bool operator < (node a, node b)
8 {
9 return a.time > b.time;
10 }*/
11 };
12 int n, m;
13 int xi[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
14 int yi[8] = {0, 1, 1, 1, 0, -1, -1, -1};
15 char map[1005][1005];
16 bool vist[1005][1005];
17 bool check(int dx, int dy)
18 {
19 if (dx >= 0 && dy >=0 && dx < n && dy < m) return true;
20 return false;
21 }
22 queue <node> q;
23 int bfs(node now, node end)
24 {
25 while (!q.empty())q.pop();
26 now.time = 0;
27 q.push(now);
28
29 for (int i = 0; i < n; i++)
30 for (int j = 0; j < m; j++)
31 vist[i][j] = false;
32 vist[now.x][now.y] = true;
33 node next, tmp;
34 bool flag = false;
35 while (!q.empty())
36 {
37 now = q.front();
38 tmp = now;
39 if (now.x == end.x && now.y == end.y) return now.time;
40 q.pop();
41 flag = false;
42 while (1)
43 {
44 next.x = tmp.x + xi[map[tmp.x][tmp.y]-'0'];
45 next.y = tmp.y + yi[map[tmp.x][tmp.y]-'0'];
46 if (check(next.x, next.y) && !vist[next.x][next.y])
47 {
48 if (next.x == end.x && next.y == end.y) return tmp.time;
49 next.time = tmp.time;
50 vist[next.x][next.y] = true;
51 q.push(next);
52 tmp = next;
53 }else break;
54 }
55 for (int i = 0; i < 8; i++)
56 {
57 next.x = now.x + xi[i];
58 next.y = now.y + yi[i];
59 if (check(next.x, next.y) && !vist[next.x][next.y])
60 {
61 if (map[now.x][now.y] - '0' == i) next.time = now.time;
62 else next.time = now.time + 1;
63 if (next.x == end.x && next.y == end.y) return next.time;
64 vist[next.x][next.y] = true;
65 q.push(next);
66 tmp = next;
67 while (1)
68 {
69 next.x = tmp.x + xi[map[tmp.x][tmp.y]-'0'];
70 next.y = tmp.y + yi[map[tmp.x][tmp.y]-'0'];
71 if (check(next.x, next.y) && !vist[next.x][next.y])
72 {
73 if (next.x == end.x && next.y == end.y) return tmp.time;
74 next.time = tmp.time;
75 vist[next.x][next.y] = true;
76 q.push(next);
77 tmp = next;
78 }else break;
79 }
80 }
81 }
82 }
83 return 0;
84 }
85 int main()
86 {
87 while (scanf("%d%d", &n, &m) != EOF)
88 {
89 int i, j;
90 for (i = 0; i < n; i++)
91 scanf("%s", map[i]);
92 int T;
93 scanf("%d", &T);
94 node now, end;
95 for (i = 0; i < T; i++)
96 {
97 scanf("%d%d%d%d", &now.x, &now.y, &end.x, &end.y);
98 now.time = 0;
99 now.x --;
100 now.y --;
101 end.x --;
102 end.y --;
103 if (now.x == end.x && now.y == end.y)
104 {
105 printf("0\n");
106 }else printf("%d\n", bfs(now, end));
107 }
108 }
109 return 0;
110 }
111
posted on 2012-04-22 20:23
路修遠 閱讀(1335)
評論(0) 編輯 收藏 引用 所屬分類:
路修遠