開啟章節選單
人口遷移
解題想法
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}};
以上三行各代表這些變數:
- 題目敘述變數 ( )、最小答案和最大答案。
- 兩個大小為 的二維陣列,代表更新值和目前狀態。
- 一個大小為 的二維陣列,代表移動變化量。
補充
我們利用 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; } } }
注意
題目敘述中有提到,值為 的土地需要跳過,務必記住哦!
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; }