解題想法#
1. 函式和變數設定#
在此題目解釋前，我們要先做好前置作業，即函式和變數的設定，以下是對此題目所設定的變數和函式：
1. 變數#
int r, c, k, m, ans_min = INT_MAX, ans_max = INT_MIN;
int upd[55][55], now[55][55];
int dir[4][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
以上三行各代表這些變數：
- 題目敘述變數 ( \(r, c, k, m\) )、最小答案和最大答案。
- 兩個大小為 \(55 \times 55\) 的二維陣列，代表更新值和目前狀態。
- 一個大小為 \(4 \times 2\) 的二維陣列，代表移動變化量。
補充
我們利用 dir[4][2] 來代表移動變化量，主要目的是使我們能簡易地閱讀程式碼，以便快速偵錯：
for (int i = 0; i < 4; i++) {
int new_x = pre_x + dir[i][0], new_y = pre_y + dir[i][1];
}
2. 函式#
bool in_range(int x, int y, int tarx, int tary) {
return x >= 1 && x <= tarx && y >= 1 && y <= tary;
}
以上函式 in_range() ，主要功用為簡化程式碼，讓複雜的檢測程式簡化為統一的函式。其函式主要回傳一個由四個 AND 判斷式組成的布林值，只要其中一個不成立，則全部不成立。
2. 模擬#
此題最重要的一環就是模擬，以程式來模擬人口移動，因此我們可以將此題目分成三個步驟：
- 計算人口移動。
- 將人口值預先放置。
- 更新人口 / 清除預先值。
以下為示意圖：
這三個步驟可以由一個 while 迴圈來表示：
while (m--) {
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= c; j++) {
if (now[i][j] == -1) continue;
for (int p = 0; p < 4; p++) {
int new_x = i + dir[p][0], new_y = j + dir[p][1];
if (in_range(new_x, new_y, r, c) && now[new_x][new_y] != -1) {
upd[new_x][new_y] += now[i][j] / k;
upd[i][j] -= now[i][j] / k;
}
}
}
}
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= c; j++) {
now[i][j] += upd[i][j];
upd[i][j] = 0;
}
}
}
注意
題目敘述中有提到，值為 \(-1\) 的土地需要跳過，務必記住哦！
3. 計算答案#
題目要求我們輸出模擬完後的最大值和最小值，因此可以將先前設定的 ans_min 至 INT_MAX， ans_max 至 INT_MIN ，最後再找出答案：
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= c; j++) {
if (now[i][j] != -1) {
ans_min = min(ans_min, now[i][j]);
ans_max = max(ans_max, now[i][j]);
}
}
}
範例程式#
#include <bits/stdc++.h>
using namespace std;
int r, c, k, m, ans_min = INT_MAX, ans_max = INT_MIN;
int upd[55][55], now[55][55];
int dir[4][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
bool in_range(int x, int y, int tarx, int tary) {
return x >= 1 && x <= tarx && y >= 1 && y <= tary;
}
int main() {
memset(upd, 0, sizeof(upd));
cin >> r >> c >> k >> m;
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= c; j++) {
cin >> now[i][j];
}
}
while (m--) {
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= c; j++) {
if (now[i][j] == -1) continue;
for (int p = 0; p < 4; p++) {
int new_x = i + dir[p][0], new_y = j + dir[p][1];
if (in_range(new_x, new_y, r, c) && now[new_x][new_y] != -1) {
upd[new_x][new_y] += now[i][j] / k;
upd[i][j] -= now[i][j] / k;
}
}
}
}
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= c; j++) {
now[i][j] += upd[i][j];
upd[i][j] = 0;
}
}
}
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= c; j++) {
if (now[i][j] != -1) {
ans_min = min(ans_min, now[i][j]);
ans_max = max(ans_max, now[i][j]);
}
}
}
cout << ans_min << '\n' << ans_max << '\n';
return 0;
}
