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}")
