803. 打磚塊

思路

給定一個二維矩陣，代表磚塊的初始樣子。
一個磚塊如果連結到頂部，或是相鄰的磚塊有連接到頂部，那它就是穩定的。
再給定一系列的hit代表打擊的位置。
每次打擊之後，有些磚塊會因此不穩定而掉落，問每次打擊會有幾個方塊因此落下。

每次打擊過後，都需要檢查各個磚塊是否還能保持穩定不掉落，這樣做很麻煩。
我們能將思路逆轉過來，用 「時光倒流」 的方式，去紀錄打擊會掉落多少磚塊。
既然說是時光倒流，那就是反過來做，具體如下：

1. 要先得到再經歷所有打擊之後版面的樣貌，因此把打擊的座標全數減 1。
   • 之所以都減，是因為打擊的座標可能原先並沒有磚塊存在，也就是無效打擊。
2. 使用洪水填充算法，將所有跟天花板連接的格子，都標記為穩定。
3. 時光倒流，倒序遍歷hit，把打擊的座標 + 1，並檢查因此有多少磚塊連接到了頂部，紀錄答案。

在時光倒流時，要先判斷恢復的磚塊是不是 1, 是的話才算作有效打擊，
在那之後，檢查四周鄰居有沒有 2 的存在，只有在鄰居存在穩定磚塊時，
自己才能作為中介將穩定狀態給擴散出去。

程式碼

洪水填充

class Solution {
public:
    vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
        int n = grid.size(), m = grid[0].size();
        for(auto& h : hits) {
            grid[h[0]][h[1]]--; // 打擊位置
        }

        auto dfs = [&](this auto&&dfs, int x, int y) -> int {
            if(x < 0 || x >= n || y < 0 || y >= m || grid[x][y] != 1) { // 0, 2, 都不會被算到, 只有 1 算
                return 0;
            }
            grid[x][y] = 2; // 走訪過的位置標記為 2, 同時也代表跟天花板相連的標記
            int sum = 1;
            sum += dfs(x - 1, y);
            sum += dfs(x + 1, y);
            sum += dfs(x, y - 1);
            sum += dfs(x, y + 1);
            return sum;
        };

        // 2.頂端一定是穩定的，利用洪水填充擴散
        for(int j = 0; j < m; j++) { 
            dfs(0, j);
        }

        // 判斷是否值得擴展，
        // 必須確保四周有 2 存在，才能將穩定狀態擴散給其他鄰居
        auto worth = [&](int x, int y) -> bool {
            return grid[x][y] == 1 && 
                   (x == 0 
                   || (x > 0 && grid[x - 1][y] == 2)
                   || (x < n - 1 && grid[x + 1][y] == 2)
                   || (y > 0 && grid[x][y - 1] == 2) 
                   || (y < m - 1 && grid[x][y + 1] == 2));
        };

        // 時光倒流
        vector<int> res(hits.size());
        int r, c;
        for(int i = hits.size() - 1; i >= 0; i--) {
            r = hits[i][0];
            c = hits[i][1];
            grid[r][c]++;   
            if(worth(r, c)) { // 有可能接上了更多節點
                res[i] = dfs(hits[i][0], hits[i][1]) - 1; // 減去被打碎的自己
            }
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(mn)$
• 空間複雜度：$O(mn)$