BZOJ2346 [Baltic 2011]Lamp
每条对角线都建一条边原来对角线有的边权为0，没有的边权为1
最短路即可
1 /**************************************************************
2 Problem: 2346
3 User: rausen
4 Language: C++
5 Result: Accepted
6 Time:1312 ms
7 Memory:29404 kb
8 ****************************************************************/
9
10 #include <cstdio>
11 #include <cstring>
12 #include <algorithm>
13 #include <queue>
14
15 using namespace std;
16 const int len = 505;
17 const int N = 300005;
18 const int M = 2000005;
19
20 struct edges {
21 int next, to, v;
22 edges() {}
23 edges(int _n, int _t, int _v) : next(_n), to(_t), v(_v) {}
24 } e;
25
26 int n, m, Tot, tot;
27 char mp;
28 int w, first, dis;
29
30 struct heap_node {
31 int v, to;
32 heap_node() {}
33 heap_node(int _v, int _to) : v(_v), to(_to) {}
34 };
35 inline bool operator < (const heap_node &a, const heap_node &b) {
36 return a.v > b.v;
37 }
38
39 priority_queue <heap_node> h;
40
41 void Add_Edges(int x, int y, int z) {
42 e[++tot] = edges(first, y, z), first = tot;
43 e[++tot] = edges(first, x, z), first = tot;
44 }
45
46 inline void add_to_heap(const int p) {
47 for (int x = first; x; x = e.next)
48 if (dis.to] == -1)
49 h.push(heap_node(e.v + dis, e.to));
50 }
51
52 void Dijkstra(int S) {
53 memset(dis, -1, sizeof(dis));
54 while (!h.empty()) h.pop();
55 dis = 0, add_to_heap(S);
56 int p;
57 while (!h.empty()) {
58 if (dis != -1) {
59 h.pop();
60 continue;
61 }
62 p = h.top().to;
63 dis = h.top().v;
64 h.pop();
65 add_to_heap(p);
66 }
67 }
68
69 void build_graph() {
70 int i, j;
71 for (i = 1; i <= n; ++i)
72 for (j = 1; j <= m; ++j)
73 if (mp == '\\') {
74 Add_Edges(w, w, 0);
75 Add_Edges(w, w, 1);
76 } else {
77 Add_Edges(w, w, 1);
78 Add_Edges(w, w, 0);
79 }
80 }
81
82 int main() {
83 int i, j;
84 scanf("%d%d", &n, &m);
85 for (i = 1; i <= n; ++i)
86 scanf("%s", mp + 1);
87 for (i = 1; i <= n + 1; ++i)
88 for (j = 1; j <= m + 1; ++j)
89 w = ++Tot;
90 build_graph();
91 Dijkstra(1);
92 if (dis != -1) printf("%d\n", dis);
93 else puts("NO SOLUTION");
94 return 0;
95 }
View Code
页:
[1]