描述

文字版

代码

class Solution {
public:
    int n, m;
    vector<int> p, sz;

    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 坐标变换
    int get(int x, int y) {
        return x * m + y;
    }

    vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
        n = grid.size(), m = grid[0].size();
        int S = n * m;
        // 用并查集 将每一位数变成集合 
        // 最后N+1位变成头部虚拟集合
        for (int i = 0; i <= S; i ++ ) p.push_back(i), sz.push_back(1);

        // 因为要倒序做 所以要将击中的砖块消除
        // st记录是否有砖块消除
        vector<bool> st;
        for (auto& p: hits) {
            int x = p[0], y = p[1];
            if (grid[x][y]) {
                grid[x][y] = 0;
                st.push_back(true);
            } else {
                st.push_back(false);
            }
        }

        // 上下左右偏移量
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                // 剩下的砖块是否和头部虚拟砖块连接
                if (grid[i][j]) {
                    int a = get(i, j);
                    // 第一层砖块要和头部虚拟砖块连接
                    if (!i) {
                        if (find(S) != find(a)) {
                            // 和头部虚拟砖块连接数量
                            sz[find(S)] += sz[find(a)];
                            p[find(a)] = find(S);
                        }
                    }
                    for (int k = 0; k < 4; k ++ ) {
                        int x = i + dx[k], y = j + dy[k];
                        // 当前点a的grid[x][y]如果存在b
                        // 证明可以和头部虚拟砖块连接
                        if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y]) {
                            int b = get(x, y);
                            if (find(a) != find(b)) {
                                // 和头部虚拟砖块连接数量
                                sz[find(b)] += sz[find(a)];
                                p[find(a)] = find(b);
                            }
                        }
                    }
                }

        vector<int> res(hits.size());
        // 记录消失砖块的最终状态
        int last = sz[find(S)];
        // 将消失的砖块加上去
        for (int i = hits.size() - 1; i >= 0; i -- )
            // 如果之前砖块掉落过
            if (st[i]) {
                int x = hits[i][0], y = hits[i][1];
                grid[x][y] = 1;
                int a = get(x, y);
                // 第一层砖块要和头部虚拟砖块连接
                if (!x) {
                    if (find(S) != find(a)) {
                        // 和头部虚拟砖块连接数量
                        sz[find(S)] += sz[find(a)];
                        p[find(a)] = find(S);
                    }
                }
                for (int j = 0; j < 4; j ++ ) {
                    int c = x + dx[j], d = y + dy[j];
                    // 当前点a的grid[x][y]如果存在b
                    // 证明可以和头部虚拟砖块连接
                    if (c >= 0 && c < n && d >= 0 && d < m && grid[c][d]) {
                        int b = get(c, d);
                        if (find(a) != find(b)) {
                            // 和头部虚拟砖块连接数量
                            sz[find(b)] += sz[find(a)];
                            p[find(a)] = find(b);
                        }
                    }
                }
                // sz[find(S)]现在的砖块数 上一次砖块数 在减1是消失的砖块
                // 答案最小值是0
                res[i] = max(0, sz[find(S)] - last - 1);
                // 记录上一次的砖块数
                last = sz[find(S)];
            }
        return res;
    }
};