【题解】HDU-6699 Block Breaker

Block Breaker (HDU - 6699)

题面

Given a rectangle frame of size n × m. Initially, the frame is strewn with n × m square blocks of size 1 × 1. Due to the friction with the frame and each other, the blocks are stable and will not drop.

However, the blocks can be knocked down. When a block is knocked down, other remaining blocks may also drop since the friction provided by other remaining blocks may not sustain them anymore. Formally, a block will drop if it is knocked or not stable, which means that at least one of the left block and the right block has been dropped and at least one of the front block and the back block has been dropped. Especially, the frame can be regarded as a huge stable block, which means that if one block’s left is the frame, only when its right block has been dropped and at least one of the front block and the back block has been dropped can it drop. The rest situations are similar.

Now you, the block breaker, want to knock down the blocks. Formally, you will do it q times. In each time, you may choose a position (xi, yi) If there remains a block at the chosen position, you will knock it down; otherwise, nothing will happen. Moreover, after knocking down the block, you will wait until no unstable blocks are going to drop and then do the next operation.

For example, please look at the following illustration, the frame is of size 2 × 2 and the block (1, 1) and (1, 2) have been dropped. If we are going to knock the block (2, 1) , not only itself but also the block (2 , 1) will drop in this knocking operation.

img

You want to know how many blocks will drop in total in each knocking operation. Specifically, if nothing happens in one operation, the answer should be regarded as 0.

输入

The first line contains one positive integer T ( 1 ≤ T ≤ 10 ) , denoting the number of test cases.

For each test case:

The first line contains three positive integers n, m and q ( 1 ≤ n , m ≤ 2000, 1 ≤ q ≤ 100000 ) , denoting the sizes in two dimensions of the frame and the number of knocking operations.

Each of the following q lines contains two positive integers xi and yi ( 1 ≤ xi ≤ n , 1 ≤ yi ≤ m ) , describing a knocking operation.

输出

For each test case, output q lines, each of which contains a non-negative integer, denoting the number of dropped blocks in the corresponding knocking operation.

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
2
2 2 3
1 1
1 2
2 2
4 4 6
1 1
1 2
2 1
2 2
4 4
3 3

样例输出

1
2
3
4
5
6
7
8
9
1
1
2
1
1
2
0
1
11

提示

思路

代码

查看代码
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
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e3 + 5;

bool vis[N][N];

int T, n, m, q;
int x, y;

struct P {
int x, y;
};

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

bool ok(int x, int y) {
if ((x + 1 > n || !vis[x + 1][y]) && (x - 1 <= 0 || !vis[x - 1][y]))
return 1;
if ((y + 1 > m || !vis[x][y + 1]) && (y - 1 <= 0 || !vis[x][y - 1]))
return 1;
return 0;
}

int solve(int x, int y) {
if (vis[x][y])
return 0;

int sum = 1;
vis[x][y] = 1;

P sp;
sp.x = x;
sp.y = y;

queue<P> q;
q.push(sp);

while (!q.empty()) {
P tp = q.front();
q.pop();

P np = tp;
for (int i = 0; i < 4; i++) {
int xi = np.x = tp.x + dx[i];
int yi = np.y = tp.y + dy[i];

if (xi <= 0 || xi > n || yi <= 0 || yi > m)
continue;

if (!vis[xi][yi] && !ok(xi, yi)) {
sum++;
q.push(np);
vis[xi][yi] = 1;
}
}
}

return sum;
}

int main(void) {

scanf("%d", &T);
while (T--) {
scanf("%d%d%d", &n, &m, &q);
memset(vis, 0, sizeof(vis));
for (int i = 0; i < q; i++) {
scanf("%d%d", &x, &y);
printf("%d\n", solve(x, y));
}
}

return 0;
}
_/_/_/_/_/ EOF _/_/_/_/_/