人口遷移 (APCS 2020-10 中級)

一個 \(R\) 列、\(C\) 行的方格平面上分布著若干城市。第 \(r\) 列、第 \(c\) 行的位置記為 \((r,c)\)；若該位置是城市，便有一個非負整數表示城市目前的人口，否則以 \(-1\) 表示。

兩座城市只有在共用一條邊時才相鄰，也就是只考慮上、下、左、右四個方向；斜對角不算相鄰。

每天的遷移規則如下：

1. 假設某座城市在這一天開始時有 \(p\) 人，令 \(q=\left\lfloor p/k\right\rfloor\)。
2. 這座城市會向它的每一座相鄰城市各遷出 \(q\) 人。若某個方向超出平面，或相鄰位置是 \(-1\)，該方向不發生遷移，也不會扣除人口。
3. 所有城市都使用這一天開始時的人口計算遷移量，所有遷移視為同時發生。同一天中稍早收到的人，不能立刻再次遷出。

請模擬 \(m\) 天，並找出第 \(m\) 天遷移完成後，人口最少與最多的城市人口。

下圖以第一筆範例說明一天的變化。箭頭上的數字表示該方向遷移的人數；叉號格不是城市。

例如左上角城市一天開始時有 \(10\) 人，所以向右、向下各遷出 \(\lfloor10/4\rfloor=2\) 人；同時，它從下方城市收到 \(\lfloor5/4\rfloor=1\) 人，因此隔天人口為 \(10-2-2+1=7\)。

輸入格式

第一行包含四個正整數 \(R,C,k,m\)。

接下來有 \(R\) 行，每行包含 \(C\) 個整數。第 \(r\) 行第 \(c\) 個整數為 \(a_{r,c}\)：

• \(a_{r,c}=-1\) 表示該位置不是城市。
• \(a_{r,c}\ge0\) 表示該城市在第 \(1\) 天遷移開始前的人口。

限制

• \(1\le R,C,m\le50\)
• \(4\le k\le50\)
• \(-1\le a_{r,c}\le100\)
• 平面上至少有一座城市。
• 所有輸入都是整數。

輸出格式

第一行輸出 \(m\) 天後，人口最少的城市人口。

第二行輸出 \(m\) 天後，人口最多的城市人口。

評分說明

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

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

範例輸入

2 3 4 1
10 2 -1
5 -1 2

範例輸出

2
7

範例解釋

一天後，四座城市的人口分別為 \(7,4,6,2\)。因此最少人口為 \(2\)，最多人口為 \(7\)。

題目來源

APCS 2020 年 10 月實作題第 2 題；規則參考 ZeroJudge f313「人口遷移」 與王一哲的題解，題目敘述與輔助圖由 AACPOJ 重新整理。