【題解】Zerojudge f313 - 2. 人口遷移

題目連結

題目大意

一張 $N \times M$ 的平面上有一些城市，給定人口遷移的規則，模擬 $D$ 天後的結果。

題解

因為人口遷移是同時發生的，如果直接更新的話會出錯。因此我們先開一個二維陣列 $delta[i][j]$ 代表這個城市在今天結束後人口會改變多少，並在大家都計算完成之後再一起去更新。其他實作細節請參考 code。

#include <bits/stdc++.h>
using namespace std;

const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m, k, days;
	cin >> n >> m >> k >> days;
	vector<vector<int>> a(n, vector<int>(m));
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			cin >> a[i][j];
		}
	}
	while(days--) {
		vector<vector<int>> delta(n, vector<int>(m));
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				for(int dir = 0; dir < 4; dir++) {
					int ni = i + dx[dir];
					int nj = j + dy[dir];
					if(ni >= 0 && ni < n && nj >= 0 && nj < m && a[ni][nj] != -1) {
						delta[ni][nj] += a[i][j] / k;
						delta[i][j] -= a[i][j] / k;
					}
				}
			}
		}
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				a[i][j] += delta[i][j];
			}
		}
	}
	int mn = INT_MAX, mx = INT_MIN;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(a[i][j] != -1) {
				mn = min(mn, a[i][j]);
				mx = max(mx, a[i][j]);
			}
		}
	}
	cout << mn << "\n" << mx << "\n";
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】Zerojudge f313 - 2. 人口遷移