C++刷LeetCode（803. 打砖块）【并查集】

糖逗

题目描述：

有一个 m x n 的二元网格，其中 1 表示砖块，0 表示空白。砖块 稳定（不会掉落）的前提是：

一块砖直接连接到网格的顶部，或者
至少有一块相邻（4 个方向之一）砖块 稳定 不会掉落时
给你一个数组 hits ，这是需要依次消除砖块的位置。每当消除 hits[i] = (rowi, coli) 位置上的砖块时，对应位置的砖块（若存在）会消失，然后其他的砖块可能因为这一消除操作而掉落。一旦砖块掉落，它会立即从网格中消失（即，它不会落在其他稳定的砖块上）。

返回一个数组 result ，其中 result[i] 表示第 i 次消除操作对应掉落的砖块数目。

注意，消除可能指向是没有砖块的空白位置，如果发生这种情况，则没有砖块掉落。

 

示例 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 * 104
hits[i].length == 2
0 <= xi <= m - 1
0 <= yi <= n - 1
所有 (xi, yi) 互不相同

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bricks-falling-when-hit
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
private:
    int len1, len2;
    vector<vector<int> >direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    vector<int>father;
    vector<int>size;
public:
    int find_root(int x){
        if(x == father[x])return x;
        return find_root(father[x]);
    }
    void merge(int x, int y){
        int temp1 = find_root(x);
        int temp2 = find_root(y);
        if(temp1 != temp2){
            father[temp1] = temp2;
            size[temp2] += size[temp1];
        }
    }
    int get_size(int x){
        int temp = find_root(x);
        return size[temp];
    }
    int get_index(int x, int y){
        return x * len2 + y;
    }
    bool in_area(int x, int y){
        return x >= 0 && x < len1 && y >= 0 && y < len2;
    }
    vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
        len1 = grid.size(), len2 = grid[0].size();
        father = vector<int>(len1*len2+1, 0);
        size = vector<int>(len1*len2+1, 1);
        //初始化father和size
        for(int i = 0; i < len1*len2+1; i++){
            father[i] = i;
        }
        //先将hit中的砖头全部击碎
        vector<vector<int> >copy = grid;
        int len = hits.size();
        for(int i = 0; i < len; i++){
            copy[hits[i][0]][hits[i][1]] = 0;
        }
        // 将下标为 0 的这一行的砖块与「屋顶」相连
        for(int i = 0; i < len2; i++){
            if(copy[0][i] == 1){
                merge(get_index(0, i), len1*len2);
            }
        }
        // 其余网格，如果是砖块向上、向左看一下，如果也是砖块，在并查集中进行合并
        for (int i = 1; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                if (copy[i][j] == 1) {
                    // 如果上方也是砖块
                    if (copy[i - 1][j] == 1) {
                        merge(get_index(i - 1, j), get_index(i, j));
                    }
                    // 如果左边也是砖块
                    if (j > 0 && copy[i][j - 1] == 1) {
                        merge(get_index(i, j - 1), get_index(i, j));
                    }
                }
            }
        }
        // 第 3 步：按照 hits 的逆序，在 copy 中补回砖块
        vector<int>res(len, 0);
        for(int i = len-1; i >= 0; i--){
            int x = hits[i][0];
            int y = hits[i][1];
            if(grid[x][y] == 0)continue;
            // 补回之前与屋顶相连的砖块数
            int store1 = get_size(len1*len2);
            // 注意：如果补回的这个结点在第 1 行，要告诉并查集它与屋顶相连
            if(x == 0) {
                merge(get_index(0, y), len1*len2);
            }
            // 在 4 个方向上看一下，如果相邻的 4 个方向有砖块，合并它们
            for(auto cha : direction){
                int newX = x + cha[0];
                int newY = y + cha[1];
                if (in_area(newX, newY) && copy[newX][newY] == 1) {
                    merge(get_index(x, y), get_index(newX, newY));
                }
            }
            // 补回之后与屋顶相连的砖块数
            int store2 = get_size(len1*len2);
            res[i] = max(0, store2 - store1 - 1);
            copy[x][y] = 1;
        }
        return res;
    }
};

参考链接：https://leetcode-cn.com/problems ... i-by-leetcode-r5kf/