HDU 3688 Searchlights（并查集）

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <queue>
 6 using namespace std;
 7 typedef long long LL;
 8 
 9 const int MAXN = 110;
10 const int MAXM = 11000;
11 
12 struct Node {
13     int a, x, y;
14     bool operator < (const Node &rhs) const {
15         if(a != rhs.a) return a < rhs.a;
16         if(x != rhs.x) return x < rhs.x;
17         return y < rhs.y;
18     }
19 } p[MAXN * MAXM];
20 
21 int mat[MAXN][MAXM];
22 int xfa[MAXM][MAXN], yfa[MAXN][MAXM];
23 int xsize[MAXM][MAXN], ysize[MAXN][MAXM];
24 int n, m, s;
25 
26 void init() {
27     for(int j = 1; j <= m; ++j)
28         for(int i = 1; i <= n; ++i) xfa[j][i] = i, xsize[j][i] = 1;
29     for(int i = 1; i <= n; ++i)
30         for(int j = 1; j <= m; ++j) yfa[i][j] = j, ysize[i][j] = 1;
31 }
32 
33 int find_set(int *fa, int x) {
34     return fa[x] == x ? x : fa[x] = find_set(fa, fa[x]);
35 }
36 
37 void merge(int *fa, int *size, int x, int y) {
38     int fx = find_set(fa, x), fy = find_set(fa, y);
39     if(size[fx] < size[fy]) swap(fx, fy);
40     size[fx] += size[fy];
41     fa[fy] = fx;
42 }
43 
44 int solve() {
45     int largest = 0;
46     for(int k = 0, i = 0; i < s; ++k) {
47         if(k - 1 >= largest) return k;
48         while(i < s && p[i].a == k) {
49             int x = p[i].x, y = p[i].y;
50             if(x - 1 >= 1 && mat[x - 1][y] <= k) merge(xfa[y], xsize[y], x - 1, x);
51             if(x + 1 <= n && mat[x + 1][y] < k) merge(xfa[y], xsize[y], x, x + 1);
52             if(y - 1 >= 1 && mat[x][y - 1] <= k) merge(yfa[x], ysize[x], y - 1, y);
53             if(y + 1 <= m && mat[x][y + 1] < k) merge(yfa[x], ysize[x], y, y + 1);
54 
55             int fx = find_set(xfa[y], x), fy = find_set(yfa[x], y);
56             if(xsize[y][fx] == n || ysize[x][fy] == m) return -1;
57 
58             if(find_set(xfa[y], 1) == fx || find_set(xfa[y], n) == fx)
59                 largest = max(largest, xsize[y][fx]);
60             else largest = max(largest, (xsize[y][fx] + 1) / 2);
61             if(find_set(yfa[x], 1) == fy || find_set(yfa[x], m) == fy)
62                 largest = max(largest, ysize[x][fy]);
63             else largest = max(largest, (ysize[x][fy] + 1) / 2);
64 
65             ++i;
66         }
67     }
68     return -1;
69 }
70 
71 int main() {
72     while(scanf("%d%d", &n, &m) != EOF) {
73         if(n == 0 && m == 0) break;
74         s = 0;
75         for(int i = 1; i <= n; ++i) {
76             for(int j = 1; j <= m; ++j) {
77                 scanf("%d", &mat[i][j]);
78                 p[s].x = i;
79                 p[s].y = j;
80                 p[s++].a = mat[i][j];
81             }
82         }
83         sort(p, p + s);
84         init();
85         int ans = solve();
86         if(ans == -1) puts("NO ANSWER!");
87         else printf("%d\n", ans);
88     }
89 }