---
# System prepended metadata

title: 實作題 - 人口遷移 - APCS - by Peter Wang
tags: [APCS]

---


# 實作題 - 人口遷移 - APCS - by Peter Wang
## 題目資訊
此題為2020.10測驗中的題目2
###### tags: `APCS` 

## 題目敘述
R×C 的平面上有一些城市，每天每個城市會向每個它相鄰的城市遷移 人數k 個人（整數除法，無條件捨去），請模擬出 m 天之後的結果，輸出人數最少及最多的城市人數。

城市人數若為 −1 則代表該位置並非城市，不能由任何城市遷移至此。

下圖是第一筆範例測資模擬的結果
![](https://i.imgur.com/gRsIwYC.png)




### 輸入：
輸入的第一行包含四個正整數 R,C,k,m,(1≤R,C,m≤50,4≤k≤50) 

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

### 輸出：
第一行，輸出在 m 天之後，人數最少的城市的人數。

第二行，輸出在 m 天之後，人數最多的城市的人數。

## 解題思路
按照題目給的資訊耐心實作，如果有比較好的解法歡迎分享。

## 程式碼
```clike=
#include<iostream>
#include<math.h>
#include<string.h>
using namespace std;
int main(){
    int r,c,k,m;
    while(cin>>r){
        cin>>c>>k>>m;
        int arr[52][52];
        int arr2[52][52];
        memset(arr,-1,sizeof(arr));
        memset(arr2,-1,sizeof(arr2));
        for(int i=1;i<=r;i++){
            for(int j=1;j<=c;j++){
                cin>>arr[i][j];
                arr2[i][j]=arr[i][j];
            }
        }
        int x=0;
        for(int p=0;p<m;p++){
            for(int i=1;i<=r;i++){
                for(int j=1;j<=c;j++){
                    x=floor(arr2[i][j]/k);
                    if(arr[i][j]==-1){
                        continue;
                    }
                    else if(i==1 && j==1){
                        if(arr[i+1][j]!=-1){
                            arr[i+1][j]+=x;
                            arr[i][j]-=x;
                        }
                        if(arr[i][j+1]!=-1){
                            arr[i][j+1]+=x;
                            arr[i][j]-=x;
                        }
                        else{
                            continue;
                        }
                    }
                    else if(i==r && j==c){
                        if(arr[i-1][j]!=-1){
                            arr[i-1][j]+=x;
                            arr[i][j]-=x;
                        }
                        if(arr[i][j-1]!=-1){
                            arr[i][j-1]+=x;
                            arr[i][j]-=x;
                        }
                        else{
                            continue;
                        }
                    }
                    else if(i==r && j==1){
                        if(arr[i-1][j]!=-1){
                            arr[i-1][j]+=x;
                            arr[i][j]-=x;
                        }
                        if(arr[i][j+1]!=-1){
                            arr[i][j+1]+=x;
                            arr[i][j]-=x;
                        }
                        else{
                            continue;
                        }
                    }
                    else if(i==1 && j==c){
                        if(arr[i+1][j]!=-1){
                            arr[i+1][j]+=x;
                            arr[i][j]-=x;
                        }
                        if(arr[i][j-1]!=-1){
                            arr[i][j-1]+=x;
                            arr[i][j]-=x;
                        }
                        else{
                            continue;
                        }
                    }
                    else if(i==1){
                        if(arr[i+1][j]!=-1){
                            arr[i+1][j]+=x;
                            arr[i][j]-=x;
                        }
                        if(arr[i][j+1]!=-1){
                            arr[i][j+1]+=x;
                            arr[i][j]-=x;
                        }
                        if(arr[i][j-1]!=-1){
                            arr[i][j-1]+=x;
                            arr[i][j]-=x;
                        }
                        else{
                            continue;
                        }
                    }
                    else if(i==r){
                        if(arr[i-1][j]!=-1){
                            arr[i-1][j]+=x;
                            arr[i][j]-=x;
                        }
                        if(arr[i][j+1]!=-1){
                            arr[i][j+1]+=x;
                            arr[i][j]-=x;
                        }
                        if(arr[i][j-1]!=-1){
                            arr[i][j-1]+=x;
                            arr[i][j]-=x;
                        }
                        else{
                            continue;
                        }
                    }
                    else if(j==1){
                        if(arr[i+1][j]!=-1){
                            arr[i+1][j]+=x;
                            arr[i][j]-=x;
                        }
                        if(arr[i][j+1]!=-1){
                            arr[i][j+1]+=x;
                            arr[i][j]-=x;
                        }
                        if(arr[i-1][j]!=-1){
                            arr[i-1][j]+=x;
                            arr[i][j]-=x;
                        }
                        else{
                            continue;
                        }
                    }
                    else if(j==c){
                        if(arr[i+1][j]!=-1){
                            arr[i+1][j]+=x;
                            arr[i][j]-=x;
                        }
                        if(arr[i][j-1]!=-1){
                            arr[i][j-1]+=x;
                            arr[i][j]-=x;
                        }
                        if(arr[i-1][j]!=-1){
                            arr[i-1][j]+=x;
                            arr[i][j]-=x;
                        }
                        else{
                            continue;
                        }
                    }
                    else{
                        if(arr[i][j-1]!=-1){
                            arr[i][j-1]+=x;
                            arr[i][j]-=x;
                        }
                        if(arr[i][j+1]!=-1){
                            arr[i][j+1]+=x;
                            arr[i][j]-=x;
                        }
                        if(arr[i-1][j]!=-1){
                            arr[i-1][j]+=x;
                            arr[i][j]-=x;
                        }
                        if(arr[i+1][j]!=-1){
                            arr[i+1][j]+=x;
                            arr[i][j]-=x;
                        }
                        else{
                            continue;
                        }
                    }
                }
            }
            memset(arr2,-1,sizeof(arr2));
            for(int i=1;i<=r;i++){
                for(int j=1;j<=c;j++){
                    arr2[i][j]=arr[i][j];
                }
            }
            memset(arr,-1,sizeof(arr));
            for(int i=1;i<=r;i++){
                for(int j=1;j<=c;j++){
                    arr[i][j]=arr2[i][j];
                }
            }
        }
        long long max=-1000000;
        long long min=1000000;
        for(int i=1;i<=r;i++){
            for(int j=1;j<=c;j++){
                if(arr[i][j]==-1){
                    continue;
                }
                if(arr[i][j]>max){
                    max=arr[i][j];
                }
                if(arr[i][j]<min){
                    min=arr[i][j];
                }
                else{
                    continue;
                }
            }
        }
        cout<<min<<endl;
        cout<<max<<endl;
    }
}
```
## 資料來源
[zerojudge](https://zerojudge.tw/)
[題目敘述](https://zerojudge.tw/ShowProblem?problemid=f313)

## 備註
>[name=PeterWang]
>[time=Fri, Jun 18, 2021 9:59 PM]