LeetCode 803. 打砖块（并查集）

示例 1：
输入：grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]
输出：[2]
解释：
网格开始为：
[[1,0,0,0]，
 [1,1,1,0]]
消除 (1,0) 处加粗的砖块，得到网格：
[[1,0,0,0]
 [0,1,1,0]]
两个加粗的砖不再稳定，因为它们不再与顶部相连，
也不再与另一个稳定的砖相邻，因此它们将掉落。得到网格：
[[1,0,0,0],
 [0,0,0,0]]
因此，结果为 [2] 。

示例 2：
输入：grid = [[1,0,0,0],[1,1,0,0]], hits = [[1,1],[1,0]]
输出：[0,0]
解释：
网格开始为：
[[1,0,0,0],
 [1,1,0,0]]
消除 (1,1) 处加粗的砖块，得到网格：
[[1,0,0,0],
 [1,0,0,0]]
剩下的砖都很稳定，所以不会掉落。网格保持不变：
[[1,0,0,0], 
 [1,0,0,0]]
接下来消除 (1,0) 处加粗的砖块，得到网格：
[[1,0,0,0],
 [0,0,0,0]]
剩下的砖块仍然是稳定的，所以不会有砖块掉落。
因此，结果为 [0,0] 。
 
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 200
grid[i][j] 为 0 或 1
1 <= hits.length <= 4 * 10^4
hits[i].length == 2
0 <= xi <= m - 1
0 <= yi <= n - 1
所有 (xi, yi) 互不相同

class dsu // 并查集
{
    int top;
    vector<int> f;
public:
    vector<int> count;//某节点对应集团的总节点个数
    dsu(int n)
    {
        f.resize(n);
        count.resize(n);
        for(int i = 0 ;i < n; ++i)
            f[i] = i, count[i] = 1;
    }
    int find(int a)
    {
        if(a == f[a])
            return a;
        return f[a] = find(f[a]);
    }
    void merge(int a, int b)
    {
        int fa = find(a), fb = find(b);
        if(fa != fb)
        {
            f[fa] = fb;
            count[fb] += count[fa];
        }
    }
};
class Solution {
public:
    vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
        int m = grid.size(), n = grid[0].size(), len = hits.size();
        vector<int> ans(len, 0);
        vector<vector<int>> copy(grid);
        for(auto& h : hits)
            copy[h[0]][h[1]] = 0;//先敲掉
        dsu u(m*n+1);
        int top = m*n;
        vector<vector<int>> dir = {{-1,0},{0,-1},{1,0},{0,1}};
        for(int j = 0; j < n; ++j)
            if(copy[0][j]==1)
                u.merge(j, top);
        for(int i = 1; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(copy[i][j]==1)
                {
                    for(int k = 0; k < 4; ++k)
                    {
                        int x = i + dir[k][0];
                        int y = j + dir[k][1];
                        if(x>=0 && x < m && y>=0 && y<n && copy[x][y]==1)
                        {
                            u.merge(x*n+y, i*n+j);
                        }
                    }
                }
            }
        }
        for(int i = len-1; i >= 0; --i)
        {
            int x0 = hits[i][0], y0 = hits[i][1];
            if(grid[x0][y0]==0)
                continue;//原来就是空的，敲了不起作用
            int ct1 = u.count[u.find(top)];// 注意要先find top 的 father
            for(int k = 0; k < 4; ++k)
            {
                int x = x0 + dir[k][0];
                int y = y0 + dir[k][1];
                if(x>=0 && x < m && y>=0 && y<n && copy[x][y]==1)
                {
                    u.merge(x*n+y, x0*n+y0);
                }
            }
            if(x0 == 0)
                u.merge(y0, top);
            ans[i] = max(0, u.count[u.find(top)]-ct1-1);
            copy[x0][y0]=1;//填回去
        }
        return ans;
    }
};