# APCS實作題2020年10月第2題：人口遷移

> 日期：2023年9月12日
> 作者：王一哲
> 題目來源：109年10月實作題
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=f313)

<br />

## 題目

### 問題描述

$R \times C$ 的平面上有一些城市，每天每個城市會向每個它相鄰的城市遷移 $\frac{人數}{k}$ 個人（整數除法，無條件捨去），請模擬出 $m$ 天之後的結果，輸出人數最少及最多的城市人數。城市人數若為 $-1$ 則代表該位置並非城市，不能由任何城市遷移至此。

下圖是第一筆範例測資模擬的結果
<img height="50%" width="50%" src="https://imgur.com/jdHDCz8.png" style="display: block; margin-left: auto; margin-right: auto;"/>

<br />

### 輸入格式

輸入的第一行包含四個正整數
$$
R, C, k, m ~(1 \leq R,~ m \leq 50,~ 4 \leq k \leq 50)
$$

接下來包含 $R$ 行，每行包含 $C$ 個整數，對於第 $i$ 行的第 $j$ 個整數 $a_{i,j} ~(-1 \leq a_{i, j} \leq 100)$ ，如果是 $-1$ 表示這個座標沒有城市，否則表示這個座標的城市人數數量，保證是非負整數。

配分
- 20%：$R=1, m=1$
- 30%：$R=1$
- 50%：無其他限制
<br />

### 輸出格式

第一行，輸出在 $m$ 天之後，人數最少的城市的人數。
第二行，輸出在 $m$ 天之後，人數最多的城市的人數。
<br />

### 範例：輸入

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

### 範例：正確輸出

2
7

<br />

## Python 程式碼

於 ZeroJudge 測試結果，最長運算時間約為 0.9 s，使用記憶體最多約為 3.5 MB，通過測試。

import sys

R, C, k, m = map(int, input().split())     # 讀取第一行資料
pop, move = [], [[0]*C for _ in range(R)]  # pop 儲存各都市人口，move 儲存每天各都市遷往相鄰都市的人數

# 讀取接下來R行資料儲存到 pop
for _ in range(R):
    pop.append(list(map(int, input().split())))

# 執行 m 次
for _ in range(m):
    # 計算每天各都市遷往相鄰都市的人數
    for i in range(R):
        for j in range(C):
            if pop[i][j] != -1:
                move[i][j] = pop[i][j] // k
    # 更新各都市的人數
    for i in range(R):
        for j in range(C):
            if pop[i][j] != -1:
                if i-1 >= 0:
                    pop[i][j] += move[i-1][j]
                    pop[i-1][j] -= move[i-1][j]
                if i+1 < R:
                    pop[i][j] += move[i+1][j]
                    pop[i+1][j] -= move[i+1][j]
                if j-1 >= 0:
                    pop[i][j] += move[i][j-1]
                    pop[i][j-1] -= move[i][j-1]
                if j+1 < C:
                    pop[i][j] += move[i][j+1]
                    pop[i][j+1] -= move[i][j+1]

# 儲存最多、最少人數的變數
maxPop = -sys.maxsize - 1
minPop = sys.maxsize

# 找出各都市中最多、最少的人數
for i in range(R):
    for j in range(C):
        if pop[i][j] != -1:
            maxPop = max(maxPop, pop[i][j])
            minPop = min(minPop, pop[i][j])

# 印出答案
print(minPop)
print(maxPop)

<br /><br />

## C++ 程式碼

於 ZeroJudge 測試結果，最長運算時間約為 5 ms，使用記憶體最多約為 344 kB，通過測試。

#include <iostream>
#include <limits.h>
#include <algorithm>
using namespace std;

int main() {
    int R, C, k, m;
    cin >> R >> C >> k >> m;   // 讀取第一行資料
    int pop[R][C], move[R][C]; // pop 儲存各都市人口，move 儲存每天各都市遷往相鄰都市的人數
    // 將 move 所有資料都設定為0
    for(int i=0; i<R; i++) {
        for(int j=0; j<C; j++) {
            move[i][j] = 0;
        }
    }
    // 讀取接下來R行資料儲存到 pop
    for(int i=0; i<R; i++) {
        for(int j=0; j<C; j++) {
            cin >> pop[i][j];
        }
    }

    // 執行 m 次
    for(int x=0; x<m; x++) {
        // 計算每天各都市遷往相鄰都市的人數
        for(int i=0; i<R; i++) {
            for(int j=0; j<C; j++) {
                if (pop[i][j] != -1) {
                    move[i][j] = pop[i][j] / k;
                }
            }
        }
        
        // 更新各都市的人數
        for(int i=0; i<R; i++) {
            for(int j=0; j<C; j++) {
                if (pop[i][j] != -1) {
                    if (i-1 >= 0) {
                        pop[i][j] += move[i-1][j];
                        pop[i-1][j] -= move[i-1][j];
                    }
                    if (i+1 < R) {
                        pop[i][j] += move[i+1][j];
                        pop[i+1][j] -= move[i+1][j];
                    }
                    if (j-1 >= 0) {
                        pop[i][j] += move[i][j-1];
                        pop[i][j-1] -= move[i][j-1];
                    }
                    if (j+1 < C) {
                        pop[i][j] += move[i][j+1];
                        pop[i][j+1] -= move[i][j+1];
                    }
                }
            }
        }
    }

    // 儲存最多、最少人數的變數
    int maxPop = INT_MIN;
    int minPop = INT_MAX;

    // 找出各都市中最多、最少的人數
    for(int i=0; i<R; i++) {
        for(int j=0; j<C; j++) {
            if (pop[i][j] != -1) {
                maxPop = max(maxPop, pop[i][j]);
                minPop = min(minPop, pop[i][j]);
            }
        }
    }

    // 印出答案
    cout << minPop << endl;
    cout << maxPop << endl;
    return 0;
}

<br /><br />

---

###### tags:`APCS`、`Python`、`C++`