動線安排 (APCS 2021-11 中級)

你是遊樂園展場的管理員。展場可以視為一個 \(m\times n\) 的方格，列編號 為 \(0\) 到 \(m-1\)，行編號為 \(0\) 到 \(n-1\)。你可以在格子中放置木樁， 並用水平或垂直的線安排參觀動線。

共有兩種操作：

• r c 0：在 \((r,c)\) 加入一根木樁。該格保證原本沒有木樁，但可能有 線經過。若有線經過，先拆掉經過該格的線，再放入木樁。接著分別向 上、下、左、右尋找該方向最近的木樁；若某方向找得到，就用線連接 新木樁與該木樁之間的所有格子。
• r c 1：移除 \((r,c)\) 的木樁。該格保證原本有木樁。木樁在上、下、 左、右四個方向連出的線段也一併拆除。

移除木樁後，不會自動把它兩側的木樁重新連起來。

水平線與垂直線可以在同一格交叉。拆除其中一個方向的線時，另一個方向 的線仍要保留。一格只要有木樁或至少一個方向的線，就占據一格面積； 交叉線也只算一格。

一開始展場中沒有木樁或線。給定 \(h\) 次操作，請求出：

1. 整個操作過程中，曾出現的最大占用面積。
2. 完成全部操作後的占用面積。

輸入格式

第一行包含三個整數 \(m,n,h\)，表示展場大小與操作次數。

接下來 \(h\) 行，每行包含三個整數 \(r,c,t\)，表示在 \((r,c)\) 執行類型 \(t\) 的操作。

限制

• \(1\le m,n\le100\)
• \(1\le h\le200\)
• \(0\le r<m\)
• \(0\le c<n\)
• \(t\in\{0,1\}\)
• 若 \(t=0\)，則 \((r,c)\) 原本沒有木樁。
• 若 \(t=1\)，則 \((r,c)\) 原本有木樁。
• 所有輸入都是整數。

輸出格式

輸出兩行：

• 第一行輸出操作過程中曾出現的最大占用面積。
• 第二行輸出完成全部操作後的占用面積。

評分說明

兩筆範例會由評測系統執行，但不計分。另有恰好 \(20\) 個計分測試組， 每組 \(5\) 分：

• 第 \(1\)～\(10\) 組（共 \(50\) 分）：\(m=1\)。
• 第 \(11\)～\(20\) 組（共 \(50\) 分）：沒有額外限制。

範例輸入 1

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

範例輸出 1

10
6

範例解釋 1

下圖中，橘色圓點表示木樁，藍線表示動線，灰色格線表示展場格子。請先 由左至右閱讀上排，再依箭頭往下，最後由右至左閱讀下排；六個小圖依序 對應六次操作。

每次操作後的占用面積依序為 \(1,3,5,8,10,6\)。第五次操作後面積達到 最大值 \(10\)。最後移除 \((2,2)\) 的木樁時，與它相連的上、左、右三段線 都被拆除；\((2,0)\) 與 \((2,4)\) 不會自動重接，因此最後面積為 \(6\)。

範例輸入 2

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

範例輸出 2

12
7

範例解釋 2

下圖使用相同符號與閱讀方式。七個小圖依序對應七次操作。

每次操作後的占用面積依序為 \(1,3,5,9,10,12,7\)。第六次操作把木樁 加入原本有水平線的 \((4,3)\)，並向上連到 \((0,3)\)。新增的垂直線在 \((2,3)\) 與既有水平線交叉，但該格只計算一次，所以面積為 \(12\)。

最後移除 \((4,3)\) 時，只拆除與這根木樁相連的線；\((2,2)\) 到 \((2,4)\) 的水平線，以及 \((2,4)\) 到 \((4,4)\) 的垂直線仍保留，因此最後面積為 \(7\)。

題目來源

APCS 2021 年 11 月實作題第 2 題；規則與範例參考 ZeroJudge g596「動線安排」 與王一哲的題解，題目敘述與 範例圖由 AACPOJ 重新整理及繪製。