APCS202111 第2題動線安排

你是一個遊樂園展場的管理員，展場是一個 m×n 的矩形，可以使用木樁和線來排動線，你可以有兩種操作

加入木樁 r c 0 加一木樁在 (r,c), 並且向他的上下左右盡量找離最近的木樁連線, 題目保證 (r,c) 上一定沒有木樁, 若 (r,c) 有線經過則先將那些線拆掉後再來連線

移除木樁 r c 1 (r,c) 拔木樁, 並把他的線也拔掉, 保證 (r,c) 上一定有木樁

總共有 h 次操作，輸出過程中有線和有木樁佔據空間的面積最大是多少, 以及 h 次操作後有線和有木樁佔據空間的面積

輸入說明

第一行輸入三個正整數 m, n 和 h 代表展場範圍是 m×n, 並且有 h 筆操作。接下來會有 h 行，每一行都有三個非負整數 r, c, t，代表在位置 (r,c) 執行操作 t

數字範圍

1≤m,n≤100

1≤h≤200

輸出說明

輸出兩個數字

第一個數字表示，操作過程中有線和有木樁佔據空間的面積最大值

第二個數字表示，操作結束後有線和有木樁佔據空間的面積

輸入範例

3 5 6

0 0 0

0 2 0

2 2 0

2 0 0

2 4 0

2 2 1

5 5 7

2 2 0

2 4 0

4 4 0

4 0 0

0 3 0

4 3 0

4 3 1

輸出範例

解題策略

模擬、二維陣列