題目連結:
題目大意:
輸入第一列給定四正整數 R 、 C 、 m 、 k (1 ≦ R 、 C 、 m ≦ 50 , 4 ≦ k ≦ 50),代表有一個 R 列 C 行的城市網格,而現在要模擬 m 天後的人口分布。
接著有 R 列的輸入,每列給定 C 個整數,代表著城市網格每格在第 0 天時的人數。當有一格的人數為 -1 時,則代表著該格並非城市,人口移動時會忽略此格。
每一天,對於每個城市,其會向每個相鄰(上下左右)的城市遷移 (前一天城市人數 ÷ k) 個人(無條件捨去,即取商數)。
求第 m 天時,所有城市中人數最少以及最多之值為何?
範例輸入:
2 3 4 1
10 2 -1
5 -1 2
範例輸出:
2
7
解題思維:
除了儲存城市網格人數的二維陣列以外,需要另一個二維陣列作為「暫存」,所有人口的更動應先存在該陣列中,所有城市做完之後才將該陣列的內容套用到城市網格。
每一次就是掃過陣列的每一格,對於每格不是 -1 之值的,掃過其相鄰城市。並對於每個相鄰城市不是 -1 的,送出 (人數 ÷ k) 個人。注意,這個更動的資訊應先存在暫存陣列裡,否則直接覆寫城市陣列會導致其他城市計算錯誤。
而上述過程要做 m 次。做完之後掃過城市網格陣列,求其中的最小值以及最大值(請記得忽略 -1 的格子),即得到所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。