挖坑跳 (AP325 P-7-10)

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

土堆與水坑的資訊可以看成一個二維矩陣，以 \(0\) 表示土堆，而 \(1\) 表示水坑，位置的標示方式以左上角為 \((1, 1)\)，右下角是 \((m, n)\)。以下是一個 \(m = 3\)、\(n = 5\) 的例子。一開始的水坑資料如下：

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

輸入格式

第一行是三個整數，依序是 \(m\)、\(n\) 與 \(k\)；接下來 \(m\) 行是土堆與水坑資料，每一行有 \(n\) 個 \(0\) 或 \(1\) 的數字，順序為由上而下、從左至右；最後一行有 \(2k\) 個數字，依序每兩個代表一個被挖成水坑的位置 \((i, j)\)，如果該位置本來就是水坑，就代表沒有動作。同一行的數字之間以空白隔開。

限制

• \(1 \le m, n \le 500\)。
• \(1 \le k \le 20000\)。
• \(1 \le i \le m\)，\(1 \le j \le n\)。

輸出格式

輸出兩行，第一行是每次最大水坑面積的總和，第二行是每次水坑數量的總和。計算總和時包含一開始的狀態，所以最多有 \(k + 1\) 次，但如果該次所挖位置本來就是水坑，代表沒有動作，該次的結果不列入總和計算。

評分說明

每筆計分測資獨立計分，每筆 5 分，共 100 分；範例不計分。

範例輸入 1

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

範例輸出 1

13
5

範例輸入 2

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

範例輸出 2

14
6

範例說明

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

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

題目來源

本題出自中正大學吳邦一教授所著《AP325－從 APCS 實作題檢測三級到五級》（v1.5）第 7 章 P-7-10，第 255 頁；經作者同意於 AACPOJ 免費公開。原題出自 TOI 入營考。教材下載：AP325 講義（Google Drive）；Python 版：AP325-Python（HackMD）。