解題報告：城市人口遷移模擬

一、題目理解

給定一個 r × c 的平面網格，每個格子可能是城市（人口為非負整數）或非城市（值為 -1）。 每一天，每個城市會向每個相鄰（上/下/左/右）且也是城市的格子遷移 floor(人口 / k) 個人（整數除法，無條件捨去）。

遷移是同時發生的：今天的遷移量都只能由「今天開始時」的人口決定，不能被同一天內已更新的結果影響。 模擬 m 天後，輸出：

1. 人口最少的城市人口
2. 人口最多的城市人口

非城市格子（-1）不能作為遷移目的地，也不需要列入最小/最大值比較。

二、核心想法：雙矩陣同步更新（避免「同一天互相影響」）

因為每天遷移要同時發生，所以必須用兩張表：

• cur：第 t 天開始時的人口（用來計算遷移量）。
• nxt：第 t 天結束後的人口（把所有遷移結果累加進來）。

每一天的流程：

1. 先令 nxt = cur（先把原本人口複製過去）。
2. 對每個城市格子 (i, j)：計算 move = cur[i][j] / k。
3. 對每個相鄰且是城市的鄰居 (nx, ny)：
   nxt[nx][ny] += move，同時 nxt[i][j] -= move。
4. 一天結束：cur = nxt。

這樣就能保證「遷移量只由當天一開始的人口 cur 決定」，符合題意的同步更新。

三、正確性說明（為什麼這樣做對）

• 同步性：所有遷移量 move 都取自 cur，而 cur 在一天內不變， 因此不會發生「先算到的城市影響後算到的城市」的錯誤。
• 流量守恆（對城市而言）：城市對每個合法鄰居送出同樣的 move，總送出量為 move × 合法鄰居數；我們在 nxt 中對每個鄰居加 move，並對自己減 move（做合法鄰居次）， 完全符合題目規則。
• 非城市處理：值為 -1 的格子永遠保持 -1，且不作為遷移目的地，也不參與 min/max。

四、複雜度分析

五、參考實作（C++）

下面是依照上述「雙矩陣同步更新」寫法整理後的版本，邏輯更直觀、也更不容易出錯。

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int r, c, k, m;
  cin >> r >> c >> k >> m;

  vector<vector<int>> cur(r, vector<int>(c));
  for (int i = 0; i < r; i++) {
    for (int j = 0; j < c; j++) {
      cin >> cur[i][j];
    }
  }

  // 四方向
  const int dx[4] = {1, -1, 0, 0};
  const int dy[4] = {0, 0, 1, -1};

  // 模擬 m 天
  for (int day = 0; day < m; day++) {
    vector<vector<int>> nxt = cur; // 同步更新：先複製

    for (int i = 0; i < r; i++) {
      for (int j = 0; j < c; j++) {
        if (cur[i][j] == -1) continue; // 非城市略過

        int move = cur[i][j] / k;      // 每個相鄰城市要送的人數
        if (move == 0) continue;       // 送 0 的話可直接略過

        for (int d = 0; d < 4; d++) {
          int ni = i + dx[d], nj = j + dy[d];
          if (ni < 0 || ni >= r || nj < 0 || nj >= c) continue;
          if (cur[ni][nj] == -1) continue; // 目的地必須是城市

          nxt[ni][nj] += move;
          nxt[i][j]   -= move;
        }
      }
    }

    cur.swap(nxt);//比較快
  }

  // 統計 m 天後的最小、最大城市人口
  int mn = INT_MAX;
  int mx = INT_MIN;

  for (int i = 0; i < r; i++) {
    for (int j = 0; j < c; j++) {
      if (cur[i][j] == -1) continue;
      mn = min(mn, cur[i][j]);
      mx = max(mx, cur[i][j]);
    }
  }

  cout << mn << "\n" << mx << "\n";
  return 0;
}

六、用題目範例快速驗算

輸入
2 3 4 1
10 2 -1
5 -1 2

輸出
2
7

程式會模擬 1 天後，掃描所有城市（排除 -1），輸出最小人口 2、最大人口 7，符合範例。