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
路修远 阅读(1296)
评论(0) 编辑 收藏 引用 所属分类:
路修远