2020/10/17 人口遷移

2023.1.25 PM 01:00 by CBJ

來源 : https://zerojudge.tw/ShowProblem?problemid=f313
出題者 : 2020年10月APCS
標籤 : 陣列操作
難易度 : 2

解題想法 : 
這題照著題目實作即可，在進行人口轉移的時候，可以開另一個陣列儲存一個回合內總共的變化，最後一次更新會比較方便。(詳見程式碼中的var[])

//C++ language

#include<iostream>
#include<vector> //vector 
#include<cstring> //memset() 
using namespace std;
int R,C,K,m;
vector<vector<int>>Map;
int var[55][55]={0};
int dir[4][2]={{0,-1},{-1,0},{0,1},{1,0}};
bool inrange(int x,int y){
    return x>=0 and x<R and y>=0 and y<C;
}
void move_out(int x,int y){
    int out_population=Map[x][y]/K;
    for(int i=0;i<4;i++){
        int nx=x+dir[i][0],ny=y+dir[i][1];
        if(inrange(nx,ny) and Map[nx][ny]!=-1){
            var[nx][ny]+=out_population;
            var[x][y]-=out_population;
        }
    }
}
int main(){
    cin>>R>>C>>K>>m;
    for(int i=0;i<R;i++){
        vector<int>tmp;
        for(int j=0;j<C;j++){
            int x; cin>>x;
            tmp.push_back(x);
        }
        Map.push_back(tmp);
    }
    for(int i=0;i<m;i++){
        memset(var,0,sizeof(var));
        for(int j=0;j<R;j++)
            for(int k=0;k<C;k++)
                if(Map[j][k]!=-1)
                    move_out(j,k);
        for(int j=0;j<R;j++)
            for(int k=0;k<C;k++)
                Map[j][k]+=var[j][k];
    }
    int max_peo=0,min_peo=1e9;
    for(vector<int>i:Map){
        for(int j:i){
            if(j==-1) continue;
            max_peo=max(max_peo,j);
            min_peo=min(min_peo,j);
        }
    }
    cout<<min_peo<<"\n"<<max_peo<<"\n";
    return 0;
}

## Python language

R,C,K,m=map(int,input().split())
Map=[]
for i in range(R): Map.append([int(x) for x in input().split()])
around=[[0,-1],[-1,0],[0,1],[1,0]]
def inrange(x,y):
    return x>=0 and x<R and y>=0 and y<C
var=[[0]*C for _ in range(R)]
def move_out(x,y):
    out_population=Map[x][y]//K
    for i in around:
        if inrange(x+i[0],y+i[1]) and Map[x+i[0]][y+i[1]]!=-1:
            var[x+i[0]][y+i[1]]+=out_population
            var[x][y]-=out_population
for i in range(m):
    var=[[0]*C for _ in range(R)]
    for j in range(len(Map)):
        for k in range(len(Map[j])):
            if Map[j][k]!=-1: move_out(j,k)
    for j in range(len(Map)):
        for k in range(len(Map[j])):
            Map[j][k]+=var[j][k]
max_peo=0
min_peo=1e18
for i in Map:
    for j in i:
        if j==-1: continue
        max_peo=max(max_peo,j)
        min_peo=min(min_peo,j)
print(f"{min_peo}\n{max_peo}")

相關文章

分享此文：