Q3. Multi Source Flood Fill

📘 題目敘述

給定兩個整數 n 和 m，分別代表網格的列數和行數。

另外給定一個二維陣列 sources，其中 sources[i] = [ri, ci, colori] 表示格子 (ri, ci) 一開始就被染成 colori。

其他所有格子一開始都還沒有上色，用 0 表示。

每一個時間步，所有目前已經上色的格子，都會同時把自己的顏色擴散到上下左右四個方向中，尚未上色 的相鄰格子。

如果同一個時間步有多個顏色同時擴散到同一個尚未上色格子，

那這個格子會選擇其中數值最大的顏色。

整個過程會一直持續到沒有新的格子可以再被染色為止。

請回傳最後整個網格的顏色狀態。

條件限制

• 1 <= n, m <= 10^5
• 1 <= n * m <= 10^5
• 1 <= sources.length <= n * m
• sources[i] = [ri, ci, colori]
• 0 <= ri <= n - 1
• 0 <= ci <= m - 1
• 1 <= colori <= 10^6
• 所有 (ri, ci) 都互不相同

🧠 解題思路

我這題的想法是用 multi-source BFS。

因為一開始就可能有很多個已經上色的起點，而且題目說每個時間步都是同時擴散，

這種「一層一層往外擴張」的感覺就很適合用 BFS 來做。

不過這題和一般 BFS 不太一樣的地方是：

• 同一層的不同顏色，可能同時碰到同一個新格子
• 如果真的同時碰到，要選顏色最大的那個

所以我這份寫法不是一看到鄰居就立刻染色，

而是先把「下一層準備被染到的格子」全部收集起來，並記錄它們這一層能拿到的最大顏色。

等這一層全部處理完之後，再一起把那些格子正式上色並丟進 queue。

這樣就能正確模擬「同一時間步同時擴散」這件事。

所有變數

• v：最後要回傳的網格，v[i][j] 表示目前這格的顏色，0 代表還沒上色
• q：BFS 用的 queue，裡面放目前這一層已經上色、接下來要往外擴散的格子
• dx：四個方向在列上的位移
• dy：四個方向在行上的位移
• cur：目前這一層 queue 裡的節點數量
• next：記錄下一層哪些格子會被染到，以及它們在同一時間步中應該拿到的最大顏色
• key：把二維座標 (x, y) 壓成一個整數，方便拿來當 unordered_map 的 key
• color：某個來源格子本身的顏色，或某個下一層格子最後決定採用的顏色

🪜 主要流程步驟

1. 先建立初始網格和 BFS 起點

我先建立一個 n × m 的網格 v，一開始全部填 0，表示都還沒上色：

vector<vector<int>> v(n, vector<int>(m, 0));

接著我把所有 sources 提供的起點都先放進去：

• 把對應位置染成指定顏色
• 再把那個位置丟進 queue

這樣一開始 queue 裡裝的，就是第 0 層已經上色、接下來要往外擴散的所有來源點。

2. 準備四個方向，之後做 BFS 擴散

因為題目只允許往上下左右四個方向擴散，所以我先準備：

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

之後每次從某個格子 (x, y) 出發，只要枚舉這四個方向，就能找到所有相鄰格子。

3. BFS 一層一層處理，確保同一時間步同時擴散

這題最重要的地方就是「同一時間步要同時擴散」，

所以我每次都先記下目前 queue 的大小：

int cur = q.size();

這表示這一輪 BFS 只處理目前這一層的格子。

而這些格子擴散出去的結果，都屬於下一個時間步。

所以我不會立刻把鄰居直接染色，

而是先開一個 next：

unordered_map<int, int> next;

它的用途是記錄：

• 下一層有哪些格子會被碰到
• 如果同一格被多個顏色同時碰到，最後該選哪個顏色

這樣就能把「同一層所有來源的影響」先收集完，再統一更新。

4. 掃目前這一層的所有格子，把下一層候選格子收集起來

對於這一層 queue 裡的每一個格子 (x, y)，

我都去看它上下左右四個方向的鄰居 (nx, ny)。

只有當這個鄰居：

• 還在邊界內
• 而且目前還沒上色，也就是 v[nx][ny] == 0

我才把它視為「下一層候選格子」。

這裡我把 (nx, ny) 壓成：

key = nx * m + ny

這樣就能用一個整數當 key，方便存進 unordered_map。

而：

next[key] = max(next[key], v[x][y]);

的意思是：

• 如果這格在這一時間步被很多不同顏色同時碰到
• 那我就保留最大的那個顏色

這正好符合題目規則。

5. 當前一層全部掃完後，再一起把下一層正式染色

等目前這一層全部處理完之後，next 裡就已經完整記錄了：

• 下一個時間步哪些格子會被染到
• 它們最後應該拿到的顏色是什麼

這時我才統一把它們正式寫進 v：

這一步有兩個作用：

• 把下一層格子真正染色
• 把它們放進 queue，讓它們在下一輪 BFS 中繼續往外擴散

這樣就能正確模擬出「先同時擴散，再一起進入下一時間步」的過程。

6. 全部染完之後回傳最後網格

當 queue 變空時，表示已經沒有新的格子可以再被染色了。

這時整個網格就是最後答案，直接回傳 v。

⏱️ 複雜度

設 N = n × m。

• 時間複雜度：O(N)

每個格子最多只會真正被染色一次，並且每次只檢查固定四個方向，所以整體是線性時間。

• 空間複雜度：O(N)

網格 v、queue，以及每一輪暫存下一層的 next，整體都和格子數量同階。

💻 程式碼實作

class Solution {
public:
    vector<vector<int>> colorGrid(int n, int m, vector<vector<int>>& sources) {
        vector<vector<int>> v(n, vector<int>(m, 0));
        queue<pair<int, int>> q;
        for (auto now : sources) {
            int x = now[0], y = now[1];
            int color = now[2];
            v[x][y] = color;
            q.push({x, y});
        }

        int dx[4] = {0, 0, 1, -1};
        int dy[4] = {1, -1, 0, 0};
        while (!q.empty()) {
            int cur = q.size();
            unordered_map<int, int> next;
            for (int i = 0; i < cur; i++) {
                auto p = q.front();
                int x = p.first, y = p.second;
                q.pop();
                for (int j = 0; j < 4; j++) {
                    int nx = x + dx[j];
                    int ny = y + dy[j];
                    if (0 <= nx && nx < n && 0 <= ny && ny < m &&
                        v[nx][ny] == 0) {
                        int key = nx * m + ny;
                        next[key] = max(next[key], v[x][y]);
                    }
                }
            }
            for (auto it : next) {
                int key = it.first;
                int color = it.second;
                int x = key / m;
                int y = key % m;

                v[x][y] = color;
                q.push({x, y});
            }
        }
        return v;
    }
};

🔗 題目連結

https://leetcode.com/contest/weekly-contest-498/problems/multi-source-flood-fill/