小雨喜歡在土堆上挖坑，在坑裡注入水之後，然後玩跳水坑的遊戲。一個庭院被畫分成m*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的水坑。
第一行是三個整數，依序是m, n 與k，接下來m行是土堆與水坑資料，每一行有n 個0或1的數字，順序為由上而下，從左至右。最後一行有 2k個數字，依序每兩個代表一個被挖成水坑的位置(i,j)，如果該位置本來就是水坑，就代表沒有動作。m與n不會超過500，k不超過20000。
輸出兩行，第一行是每次最大水坑面積的總和(包含一開始，所以有k+1次)，第二行是每次水坑數量的總和。
3 5 1 1 0 0 1 1 0 1 1 0 1 1 1 0 0 1 2 4
13 5
這是題目敘述中的例子，一開始有3個水坑，大小是(1,4,4)，操作一次後變2個水坑，大小是(1,9)。最大水坑面積總和是4+9=13，水坑數樣總和是3+2=5。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||