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

糖逗

题目描述：

1. 有一个 m x n 的二元网格，其中 1 表示砖块，0 表示空白。砖块 稳定（不会掉落）的前提是：
   
2. 
   
3. 一块砖直接连接到网格的顶部，或者
   
4. 至少有一块相邻（4 个方向之一）砖块 稳定 不会掉落时
   
5. 给你一个数组 hits ，这是需要依次消除砖块的位置。每当消除 hits[i] = (rowi, coli) 位置上的砖块时，对应位置的砖块（若存在）会消失，然后其他的砖块可能因为这一消除操作而掉落。一旦砖块掉落，它会立即从网格中消失（即，它不会落在其他稳定的砖块上）。
   
6. 
   
7. 返回一个数组 result ，其中 result[i] 表示第 i 次消除操作对应掉落的砖块数目。
   
8. 
   
9. 注意，消除可能指向是没有砖块的空白位置，如果发生这种情况，则没有砖块掉落。
   
10. 
    
11.  
    
12. 
    
13. 示例 1：
    
14. 
    
15. 输入：grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]
    
16. 输出：[2]
    
17. 解释：
    
18. 网格开始为：
    
19. [[1,0,0,0]，
    
20. [1,1,1,0]]
    
21. 消除 (1,0) 处加粗的砖块，得到网格：
    
22. [[1,0,0,0]
    
23. [0,1,1,0]]
    
24. 两个加粗的砖不再稳定，因为它们不再与顶部相连，也不再与另一个稳定的砖相邻，因此它们将掉落。得到网格：
    
25. [[1,0,0,0],
    
26. [0,0,0,0]]
    
27. 因此，结果为 [2] 。
    
28. 示例 2：
    
29. 
    
30. 输入：grid = [[1,0,0,0],[1,1,0,0]], hits = [[1,1],[1,0]]
    
31. 输出：[0,0]
    
32. 解释：
    
33. 网格开始为：
    
34. [[1,0,0,0],
    
35. [1,1,0,0]]
    
36. 消除 (1,1) 处加粗的砖块，得到网格：
    
37. [[1,0,0,0],
    
38. [1,0,0,0]]
    
39. 剩下的砖都很稳定，所以不会掉落。网格保持不变：
    
40. [[1,0,0,0],
    
41. [1,0,0,0]]
    
42. 接下来消除 (1,0) 处加粗的砖块，得到网格：
    
43. [[1,0,0,0],
    
44. [0,0,0,0]]
    
45. 剩下的砖块仍然是稳定的，所以不会有砖块掉落。
    
46. 因此，结果为 [0,0] 。
    
47.  
    
48. 
    
49. 提示：
    
50. 
    
51. m == grid.length
    
52. n == grid[i].length
    
53. 1 <= m, n <= 200
    
54. grid[i][j] 为 0 或 1
    
55. 1 <= hits.length <= 4 * 104
    
56. hits[i].length == 2
    
57. 0 <= xi&#160;<= m - 1
    
58. 0 <=&#160;yi <= n - 1
    
59. 所有 (xi, yi) 互不相同
    
60. 
    
61. 来源：力扣（LeetCode）
    
62. 链接：https://leetcode-cn.com/problems/bricks-falling-when-hit
    
63. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. private:
   
3.     int len1, len2;
   
4.     vector<vector<int> >direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
   
5.     vector<int>father;
   
6.     vector<int>size;
   
7. public:
   
8.     int find_root(int x){
   
9.         if(x == father[x])return x;
   
10.         return find_root(father[x]);
    
11.     }
    
12.     void merge(int x, int y){
    
13.         int temp1 = find_root(x);
    
14.         int temp2 = find_root(y);
    
15.         if(temp1 != temp2){
    
16.             father[temp1] = temp2;
    
17.             size[temp2] += size[temp1];
    
18.         }
    
19.     }
    
20.     int get_size(int x){
    
21.         int temp = find_root(x);
    
22.         return size[temp];
    
23.     }
    
24.     int get_index(int x, int y){
    
25.         return x * len2 + y;
    
26.     }
    
27.     bool in_area(int x, int y){
    
28.         return x >= 0 && x < len1 && y >= 0 && y < len2;
    
29.     }
    
30.     vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
    
31.         len1 = grid.size(), len2 = grid[0].size();
    
32.         father = vector<int>(len1*len2+1, 0);
    
33.         size = vector<int>(len1*len2+1, 1);
    
34.         //初始化father和size
    
35.         for(int i = 0; i < len1*len2+1; i++){
    
36.             father[i] = i;
    
37.         }
    
38.         //先将hit中的砖头全部击碎
    
39.         vector<vector<int> >copy = grid;
    
40.         int len = hits.size();
    
41.         for(int i = 0; i < len; i++){
    
42.             copy[hits[i][0]][hits[i][1]] = 0;
    
43.         }
    
44.         // 将下标为 0 的这一行的砖块与「屋顶」相连
    
45.         for(int i = 0; i < len2; i++){
    
46.             if(copy[0][i] == 1){
    
47.                 merge(get_index(0, i), len1*len2);
    
48.             }
    
49.         }
    
50.         // 其余网格，如果是砖块向上、向左看一下，如果也是砖块，在并查集中进行合并
    
51.         for (int i = 1; i < len1; i++) {
    
52.             for (int j = 0; j < len2; j++) {
    
53.                 if (copy[i][j] == 1) {
    
54.                     // 如果上方也是砖块
    
55.                     if (copy[i - 1][j] == 1) {
    
56.                         merge(get_index(i - 1, j), get_index(i, j));
    
57.                     }
    
58.                     // 如果左边也是砖块
    
59.                     if (j > 0 && copy[i][j - 1] == 1) {
    
60.                         merge(get_index(i, j - 1), get_index(i, j));
    
61.                     }
    
62.                 }
    
63.             }
    
64.         }
    
65.         // 第 3 步：按照 hits 的逆序，在 copy 中补回砖块
    
66.         vector<int>res(len, 0);
    
67.         for(int i = len-1; i >= 0; i--){
    
68.             int x = hits[i][0];
    
69.             int y = hits[i][1];
    
70.             if(grid[x][y] == 0)continue;
    
71.             // 补回之前与屋顶相连的砖块数
    
72.             int store1 = get_size(len1*len2);
    
73.             // 注意：如果补回的这个结点在第 1 行，要告诉并查集它与屋顶相连
    
74.             if(x == 0) {
    
75.                 merge(get_index(0, y), len1*len2);
    
76.             }
    
77.             // 在 4 个方向上看一下，如果相邻的 4 个方向有砖块，合并它们
    
78.             for(auto cha : direction){
    
79.                 int newX = x + cha[0];
    
80.                 int newY = y + cha[1];
    
81.                 if (in_area(newX, newY) && copy[newX][newY] == 1) {
    
82.                     merge(get_index(x, y), get_index(newX, newY));
    
83.                 }
    
84.             }
    
85.             // 补回之后与屋顶相连的砖块数
    
86.             int store2 = get_size(len1*len2);
    
87.             res[i] = max(0, store2 - store1 - 1);
    
88.             copy[x][y] = 1;
    
89.         }
    
90.         return res;
    
91.     }
    
92. };

复制代码

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