TopCoder

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Tags

Description

粉紅豬佩佩喜歡跳水坑,他會在土堆上挖坑,在坑內注入水之後開始玩跳水坑的遊戲。佩佩的庭院被劃分成 $M \times N$ 個大小相同的方格,每個方格可能是土堆或水坑,一個水坑格子會和上下左右四個方向的水坑格子被視為一個連通的水坑,我們要幫佩佩計算庭院內共有幾個水坑以及最大的水坑站有幾個格子。

除了一開始的水坑格子外,佩佩每次會指定將一個格子變成水坑格子,如果這個格子是新被挖出來的水坑格子,就有可能將附近的水坑連在一起變成一個更大的水坑。佩佩一共挖了 $K$ 次,請你計算出每一次挖了之後的水坑數與最大的水坑面積。

土堆與水坑的資訊可以看成一個二維矩陣,並以 $0$ 表示土堆,以 $1$ 表示水坑,位置的標示以左上角為 $(1, 1)$,右下角為 $(M, N)$。以下是一個 $M = 3, N = 5$ 的例子,一開始的水坑資料如下:

$1$
$0$
$0$
$\boldsymbol{1}$
$\boldsymbol{1}$
$0$
$\boldsymbol{1}$
$\boldsymbol{1}$
$\color{red}{\boldsymbol{0}}$
$\boldsymbol{1}$
$\boldsymbol{1}$
$\boldsymbol{1}$
$0$
$0$
$\boldsymbol{1}$

一開始有三個水坑:左上角只佔據 $1$ 格的水坑、左下有一個 $4$ 格的水坑、以及右方有一個 $4$ 格的水坑。現在假設佩佩將 $(2, 4)$ 處的土堆改成水坑(紅色粗體處),那麼左下和右方的水坑就會連接成一個大小為 $9$ 的水坑。

Input Format

輸入第一行有三個整數 $M, N, K (1 \leq M, N \leq 500, 1 \leq K \leq 20000)$,分別代表庭院的形狀以及事件次數。

接下來 $M$ 行是庭院的資訊,每一行有 $N$ 個 $0$ 或 $1$ 的數字,順序由上至下,由左至右分別代表每一個格子的資訊。
接下來 $K$ 行,每一行各有兩個數字 $x, y$,代表每一個被挖成水坑的位置 $(x, y)$。如果該位置本來就是水坑,則不會有任何動作發生。

Output Format

請輸出兩行,第一行是每次最大水坑面積的總和(包含一開始,所以共有 $K + 1$ 次)。第二行請輸出每次水坑個數的總和。

Sample Input 1

3 5 1
1 0 0 1 1
0 1 1 0 1
1 1 0 0 1
2 4

Sample Output 1

13
5

Sample Input 2

2 6 2
0 1 1 0 1 1
0 1 0 0 0 1
2 4
1 4

Sample Output 2

14
6

Hints

Problem Source

TOI 入營考

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~28 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
21 1000 524288 65536 2
22 1000 524288 65536 2
23 1000 524288 65536 2
24 1000 524288 65536 2
25 1000 524288 65536 2
26 1000 524288 65536 2
27 1000 524288 65536 2
28 1000 524288 65536 2