LeetCode:803. Bricks Falling When Hit打砖块（C语言）

àì夳堔傛蜴生んèń 2023-01-07 07:18 111阅读 0赞

**题目描述：**  
有一个 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  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。  
**解答：**

/** * Note: The returned array must be malloced, assume caller calls free(). */
    int find(int* f, int x) { 
        if (f[x] == x) { 
            return x;
        }
        int newf = find(f, f[x]);
        f[x] = newf;
        return f[x];
    }
    
    void merge(int* f, int* sz, int x, int y) { 
        int fx = find(f, x), fy = find(f, y);
        if (fx == fy) { 
            return;
        }
        f[fx] = fy;
        sz[fy] += sz[fx];
    }
    
    int size(int* f, int* sz, int x) { 
        return sz[find(f, x)];
    }
    
    int* hitBricks(int** grid, int gridSize, int* gridColSize, int** hits, int hitsSize, int* hitsColSize, int* returnSize) { 
        int h = gridSize, w = gridColSize[0];
    
        int f[h * w + 1], sz[h * w + 1];
        for (int i = 0; i <= h * w; i++) { 
            f[i] = i;
            sz[i] = 1;
        }
        int status[h][w];
        for (int i = 0; i < h; i++) { 
            for (int j = 0; j < w; j++) { 
                status[i][j] = grid[i][j];
            }
        }
        for (int i = 0; i < hitsSize; i++) { 
            status[hits[i][0]][hits[i][1]] = 0;
        }
        for (int i = 0; i < h; i++) { 
            for (int j = 0; j < w; j++) { 
                if (status[i][j] == 1) { 
                    if (i == 0) { 
                        merge(f, sz, h * w, i * w + j);
                    }
                    if (i > 0 && status[i - 1][j] == 1) { 
                        merge(f, sz, i * w + j, (i - 1) * w + j);
                    }
                    if (j > 0 && status[i][j - 1] == 1) { 
                        merge(f, sz, i * w + j, i * w + j - 1);
                    }
                }
            }
        }
        int directions[4][2] = { { 0, 1}, { 1, 0}, { 0, -1}, { -1, 0}};
        int* ret = malloc(sizeof(int) * hitsSize);
        memset(ret, 0, sizeof(int) * hitsSize);
        *returnSize = hitsSize;
        memset(ret, 0, hitsSize);
        for (int i = hitsSize - 1; i >= 0; i--) { 
            int r = hits[i][0], c = hits[i][1];
            if (grid[r][c] == 0) { 
                continue;
            }
            int prev = size(f, sz, h * w);
    
            if (r == 0) { 
                merge(f, sz, c, h * w);
            }
            for (int i = 0; i < 4; i++) { 
                int nr = r + directions[i][0], nc = c + directions[i][1];
    
                if (nr >= 0 && nr < h && nc >= 0 && nc < w) { 
                    if (status[nr][nc] == 1) { 
                        merge(f, sz, r * w + c, nr * w + nc);
                    }
                }
            }
            ret[i] = fmax(0, size(f, sz, h * w) - prev - 1);
            status[r][c] = 1;
        }
        return ret;
    }

**运行结果：**  
![在这里插入图片描述][2021011608465238.png_pic_center]

**Notes：**  
参考官方文档：[https://leetcode-cn.com/problems/bricks-falling-when-hit/solution/803-da-zhuan-kuai-by-leetcode-r5kf/][https_leetcode-cn.com_problems_bricks-falling-when-hit_solution_803-da-zhuan-kuai-by-leetcode-r5kf]

[2021011608465238.png_pic_center]: /images/20221119/929649ee6b9443688d4aef93ebc76e35.png
[https_leetcode-cn.com_problems_bricks-falling-when-hit_solution_803-da-zhuan-kuai-by-leetcode-r5kf]: https://leetcode-cn.com/problems/bricks-falling-when-hit/solution/803-da-zhuan-kuai-by-leetcode-r5kf/