13.7 同時發生:讀舊表、寫新表
有一類題目的規則寫著「所有 X 同時進行」、「以這一回合開始時的狀態計算」。這句話在提醒你:不能一邊算一邊改同一張表,否則排在後面的格子會用到前面的格子剛改過的新值。解法永遠是兩張表——讀舊表、寫新表、一回合結束再交換。
¶例題:人口遷移(APCS 2020 年 10 月中級)
題目:R \times C 的平面(1 \le R, C, m \le 50),-1 表示不是城市,其餘是城市目前人口(0 \sim 100)。兩城市只在共用一條邊時相鄰。每天:① 城市在這一天開始時有 p 人,令 q = \lfloor p / k \rfloor(4 \le k \le 50)② 向每一座相鄰城市各遷出 q 人(出界或 -1 的方向不遷)③ 所有城市都用這一天開始時的人口計算,所有遷移同時發生。模擬 m 天,輸出最後人口最少與最多的城市人口。
#include <bits/stdc++.h>
using namespace std;
// 四鄰格的方向表:上、下、左、右
const int dr[4] = {-1, 1, 0, 0};
const int dc[4] = {0, 0, -1, 1};
int main() {
int R, C, k, m;
cin >> R >> C >> k >> m;
vector<vector<int>> population(R, vector<int>(C));
for (int r = 0; r < R; r++)
for (int c = 0; c < C; c++) cin >> population[r][c];
for (int day = 0; day < m; day++) {
vector<vector<int>> outgoing(R, vector<int>(C)); // 每座城市今天向每個鄰居遷出多少人
vector<vector<int>> next = population; // 新的一張表,從舊表複製開始
for (int r = 0; r < R; r++)
for (int c = 0; c < C; c++)
if (population[r][c] != -1)
outgoing[r][c] = population[r][c] / k;
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (population[r][c] == -1) continue; // 不是城市
for (int d = 0; d < 4; d++) {
const int nr = r + dr[d];
const int nc = c + dc[d];
if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue; // 出界不遷
if (population[nr][nc] == -1) continue; // 鄰格不是城市不遷
next[r][c] -= outgoing[r][c]; // 讀舊表 population、寫新表 next
next[nr][nc] += outgoing[r][c];
}
}
}
population.swap(next); // 一天結束:新表變成舊表
}
int minimum = INT_MAX;
int maximum = -1;
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (population[r][c] == -1) continue;
minimum = min(minimum, population[r][c]);
maximum = max(maximum, population[r][c]);
}
}
cout << minimum << '\n' << maximum << '\n';
return 0;
}
整段程式只讀 population(舊表)、只改 next(新表),一天結束用 swap 交換(10.6)。遷出量 outgoing 也是先用舊表算好——它是「這一天開始時」的人口決定的。
魔王迷宮的「同時判定」是同一件事的另一種長相:那裡沒有另開一張表,而是把「要清掉的格子」先記在一個 vector 裡、全部判完再清——延後套用和雙表,目的都是讓所有人看到的是回合開始時的狀態。