a125. P_7_10 挖坑跳 (@@) (TOI入營考)

Content

小雨喜歡在土堆上挖坑，在坑裡注入水之後，然後玩跳水坑的遊戲。一個庭院被畫分成 $m \times n$ 個相同大小的矩陣方格，每一個格子可能是土堆或水坑，一個水坑格子與其上下左右四個方向的水坑格子被視為連通的同一個水坑。我們需要計算有多少個水坑以及最大的水坑佔多少個格子。除了一開始的土堆與水坑，小雨每次會指定將某個格子變成水坑，如果這個方格是新挖出來的水坑，有可能把附近的水坑連在一起。小雨一共挖了 $k$ 次，請你計算出每一次挖了之後的水坑數與最大水坑面積。
土堆與水坑的資訊可以看成一個二維矩陣，以 0 表示土堆，而 1 表示水坑，位置的標示方式以左上角為 $(1, 1)$ ，右下角是 $(m, n)$ 。以下是一個 $m = 3, n = 5$ 的例子。一開始的水坑資料如下：

1 0 0 1 1

0 1 1 0 1

1 1 0 0 1

我們可以看出來有 $3$ 個水坑：左上角只佔 $1$ 格的水坑，左下有一個 $4$ 格的水坑，以及右方有一個 $4$ 格的水坑。假設現在小雨把 $(2, 4)$ 的土堆改成水坑，左下與右方的水坑便會連接成一個面積為 $9$ 的水坑。

Input

第一行是三個整數，依序是 $m, n$ 與 $k$

接下來 $m$ 行是土堆與水坑資料，每一行有 $n$ 個 0 或 1 的數字，順序為由上而下，從左至右。

最後一行有 $2 k$ 個數字，依序每兩個代表一個被挖成水坑的位置 $(i, j)$ ，如果該位置本來就是水坑，就代表沒有動作。

$m$ 與 $n$ 不會超過 $500$ ， $k$ 不超過 $20000$ 。

Output

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

Sample Input #1

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

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (20%): 1.0s , <1M
公開測資點#1 (20%): 1.0s , <1M
公開測資點#2 (20%): 1.0s , <1M
公開測資點#3 (20%): 1.0s , <1M
公開測資點#4 (20%): 1.0s , <1M

Hint ：

範例一說明：這是題目敘述中的例子，一開始有 $3$ 個水坑，大小是 $(1, 4, 4)$ ，操作一次後變 $2$ 個水坑，大小是 $(1, 9)$ 。最大水坑面積總和是 $4 + 9 = 13$ ，水坑數樣總和是 $3 + 2 = 5$ 。

範例二說明：一開始有 $2$ 個水坑，面積是 $(3, 3)$ ，第一次操作後有 $3$ 個水坑，面積是 $(3, 3, 1)$ ，第二次操作後變成一個面積 $8$ 的水坑。

Tags:

ch7

出處:

Prof.Wu [管理者： s710426(?0_o)//) ]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」