BZOJ2346 [Baltic 2011]Lamp

zzgzyyz

　　每条对角线都建一条边
　　原来对角线有的边权为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[M];
25  
26 int n, m, Tot, tot;
27 char mp[len][len];
28 int w[len][len], first[N], dis[N];
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[x], y, z), first[x] = tot;
43     e[++tot] = edges(first[y], x, z), first[y] = tot;
44 }
45  
46 inline void add_to_heap(const int p) {
47     for (int x = first[p]; x; x = e[x].next)
48         if (dis[e[x].to] == -1)
49             h.push(heap_node(e[x].v + dis[p], e[x].to));
50 }
51  
52 void Dijkstra(int S) {
53     memset(dis, -1, sizeof(dis));
54     while (!h.empty()) h.pop();
55     dis[S] = 0, add_to_heap(S);
56     int p;
57     while (!h.empty()) {
58         if (dis[h.top().to] != -1) {
59             h.pop();
60             continue;
61         }
62         p = h.top().to;
63         dis[p] = 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[j] == '\\') {
74                 Add_Edges(w[j], w[i + 1][j + 1], 0);
75                 Add_Edges(w[i + 1][j], w[j + 1], 1);
76             } else {
77                 Add_Edges(w[j], w[i + 1][j + 1], 1);
78                 Add_Edges(w[i + 1][j], w[j + 1], 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[j] = ++Tot;
90     build_graph();
91     Dijkstra(1);
92     if (dis[Tot] != -1) printf("%d\n", dis[Tot]);
93     else puts("NO SOLUTION");
94     return 0;
95 }
View Code