UVa 1665 - Islands

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給一個地勢圖,詢問若高度低於 x 時,有多少連通子圖。

Sample Input

1
2
3
4
5
6
7
8
1 
4 5
1 2 3 3 1
1 3 2 2 1
2 1 3 4 3
1 2 2 2 2
5
1 2 3 4 5

Sample Output

1
2 3 1 0 0

Solution

由於詢問操作的 x 是嚴格遞增,可以發現盤面上的元素越來越少。如果反過來操作,從高度 x 由大到小開始詢問,就可以發現元素越來越多,同時是一個聯集的操作,如此一來可以使用并查集運行。

把每一個高度位置,從高到低排序,針對詢問依序將地點放置進去,每次的放置必須與相鄰存在的元素進行聯集。

為了加快速度

  • 使用基數排序,加快對於一開始需要的排序成本,已達到線性需求。
  • 優化輸入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;

#define MAXN 1024
int g[MAXN][MAXN], h[131072], out[131072];
int parent[MAXN * MAXN], weight[MAXN * MAXN];

struct Pos {
int x, y, h;
Pos(int a = 0, int b = 0, int c = 0):
x(a), y(b), h(c) {}
bool operator<(const Pos &a) const {
return h > a.h;
}
};

int findp(int x) {
return parent[x] == x ? x : parent[x] = findp(parent[x]);
}
int joint(int x, int y) {
x = findp(x), y = findp(y);
if (x == y) return 0;
if (weight[x] > weight[y])
weight[x] += weight[y], parent[y] = x;
else
weight[y] += weight[x], parent[x] = y;
return 1;
}

Pos D[MAXN * MAXN], TMP[MAXN * MAXN];
void RadixSort(Pos *A, Pos *B, int n) {
int a, x, d, C[256];
Pos *T;
for(x = 0; x < 4; x++) {
d = x * 8;
for(a = 0; a < 256; a++) C[a] = 0;
for(a = n-1; a >= 0; a--) C[(A[a].h>>d)&255]++;
for(a = 256 - 2; a >= 0; a--) C[a] += C[a+1];
for(a = n-1; a >= 0; a--) B[--C[(A[a].h>>d)&255]] = A[a];
T = A, A = B, B = T;
}
}
inline int readchar() {
const int N = 1048576;
static char buf[N];
static char *p = buf, *end = buf;
if(p == end) {
if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
p = buf;
}
return *p++;
}
inline int ReadInt(int *x) {
static char c, neg;
while((c = readchar()) < '-') {if(c == EOF) return 0;}
neg = (c == '-') ? -1 : 1;
*x = (neg == 1) ? c-'0' : 0;
while((c = readchar()) >= '0')
*x = (*x << 3) + (*x << 1) + c-'0';
*x *= neg;
return 1;
}
int main() {
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int testcase, n, m, q, tx, ty;
// scanf("%d", &testcase);
ReadInt(&testcase);
while (testcase--) {
// scanf("%d %d", &n, &m);
ReadInt(&n);
ReadInt(&m);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
// scanf("%d", &g[i][j]);
ReadInt(&g[i][j]);
// scanf("%d", &q);
ReadInt(&q);
for (int i = 0; i < q; i++)
// scanf("%d", &h[i]);
ReadInt(&h[i]);

int didx = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
D[didx++] = Pos(i, j, g[i][j]);
}
}
RadixSort(D, TMP, n*m);
int idx = 0, nm = n*m, sum = 0;
Pos u;
for (int i = nm; i >= 0; i--)
parent[i] = i, weight[i] = 1;
for (int i = q - 1; i >= 0; i--) {
while (idx < nm && D[idx].h > h[i]) {
sum++;
u = D[idx++];
// printf("add %d %d - %d\n", u.x, u.y, u.h);
for (int j = 0; j < 4; j++) {
tx = u.x + dx[j], ty = u.y + dy[j];
if (tx < 0 || ty < 0 || tx >= n || ty >= m)
continue;
if (g[tx][ty] > h[i]) {
sum -= joint(u.x * m + u.y, tx * m + ty);
}
}
}
out[i] = sum;
// printf("%d\n", sum);
}
for (int i = 0; i < q; i++)
printf("%d ", out[i]);
puts("");
}
return 0;
}