語法書 / AA 競程語法書 下冊 / 第十三單元 / 同時發生:讀舊表、寫新表

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 \rfloor4 \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 裡、全部判完再清——延後套用雙表,目的都是讓所有人看到的是回合開始時的狀態。