代码拉取完成，页面将自动刷新
同步操作将从 doocs/leetcode 强制同步，此操作会覆盖自 Fork 仓库以来所做的任何修改，且无法恢复！！！
确定后同步将在后台操作，完成时将刷新页面，请耐心等待。
You are given an m x n binary grid, where each 1 represents a brick and 0 represents an empty space. A brick is stable if:
You are also given an array hits, which is a sequence of erasures we want to apply. Each time we want to erase the brick at the location hits[i] = (rowi, coli). The brick on that location (if it exists) will disappear. Some other bricks may no longer be stable because of that erasure and will fall. Once a brick falls, it is immediately erased from the grid (i.e., it does not land on other stable bricks).
Return an array result, where each result[i] is the number of bricks that will fall after the ith erasure is applied.
Note that an erasure may refer to a location with no brick, and if it does, no bricks drop.
Example 1:
Input: grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]] Output: [2] Explanation: Starting with the grid: [[1,0,0,0], [1,1,1,0]] We erase the underlined brick at (1,0), resulting in the grid: [[1,0,0,0], [0,1,1,0]] The two underlined bricks are no longer stable as they are no longer connected to the top nor adjacent to another stable brick, so they will fall. The resulting grid is: [[1,0,0,0], [0,0,0,0]] Hence the result is [2].
Example 2:
Input: grid = [[1,0,0,0],[1,1,0,0]], hits = [[1,1],[1,0]] Output: [0,0] Explanation: Starting with the grid: [[1,0,0,0], [1,1,0,0]] We erase the underlined brick at (1,1), resulting in the grid: [[1,0,0,0], [1,0,0,0]] All remaining bricks are still stable, so no bricks fall. The grid remains the same: [[1,0,0,0], [1,0,0,0]] Next, we erase the underlined brick at (1,0), resulting in the grid: [[1,0,0,0], [0,0,0,0]] Once again, all remaining bricks are still stable, so no bricks fall. Hence the result is [0,0].
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 200grid[i][j] is 0 or 1.1 <= hits.length <= 4 * 104hits[i].length == 20 <= xi <= m - 10 <= yi <= n - 1(xi, yi) are unique.class Solution:
def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
def union(a, b):
pa, pb = find(a), find(b)
if pa != pb:
size[pb] += size[pa]
p[pa] = pb
m, n = len(grid), len(grid[0])
p = list(range(m * n + 1))
size = [1] * len(p)
g = deepcopy(grid)
for i, j in hits:
g[i][j] = 0
for j in range(n):
if g[0][j] == 1:
union(j, m * n)
for i in range(1, m):
for j in range(n):
if g[i][j] == 0:
continue
if g[i - 1][j] == 1:
union(i * n + j, (i - 1) * n + j)
if j > 0 and g[i][j - 1] == 1:
union(i * n + j, i * n + j - 1)
ans = []
for i, j in hits[::-1]:
if grid[i][j] == 0:
ans.append(0)
continue
g[i][j] = 1
prev = size[find(m * n)]
if i == 0:
union(j, m * n)
for a, b in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n and g[x][y] == 1:
union(i * n + j, x * n + y)
curr = size[find(m * n)]
ans.append(max(0, curr - prev - 1))
return ans[::-1]
class Solution {
private int[] p;
private int[] size;
public int[] hitBricks(int[][] grid, int[][] hits) {
int m = grid.length;
int n = grid[0].length;
p = new int[m * n + 1];
size = new int[m * n + 1];
for (int i = 0; i < p.length; ++i) {
p[i] = i;
size[i] = 1;
}
int[][] g = new int[m][n];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
g[i][j] = grid[i][j];
}
}
for (int[] h : hits) {
g[h[0]][h[1]] = 0;
}
for (int j = 0; j < n; ++j) {
if (g[0][j] == 1) {
union(j, m * n);
}
}
for (int i = 1; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (g[i][j] == 0) {
continue;
}
if (g[i - 1][j] == 1) {
union(i * n + j, (i - 1) * n + j);
}
if (j > 0 && g[i][j - 1] == 1) {
union(i * n + j, i * n + j - 1);
}
}
}
int[] ans = new int[hits.length];
int[] dirs = {-1, 0, 1, 0, -1};
for (int k = hits.length - 1; k >= 0; --k) {
int i = hits[k][0];
int j = hits[k][1];
if (grid[i][j] == 0) {
continue;
}
g[i][j] = 1;
int prev = size[find(m * n)];
if (i == 0) {
union(j, m * n);
}
for (int l = 0; l < 4; ++l) {
int x = i + dirs[l];
int y = j + dirs[l + 1];
if (x >= 0 && x < m && y >= 0 && y < n && g[x][y] == 1) {
union(i * n + j, x * n + y);
}
}
int curr = size[find(m * n)];
ans[k] = Math.max(0, curr - prev - 1);
}
return ans;
}
private int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
private void union(int a, int b) {
int pa = find(a);
int pb = find(b);
if (pa != pb) {
size[pb] += size[pa];
p[pa] = pb;
}
}
}
class Solution {
public:
vector<int> p;
vector<int> size;
vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
int m = grid.size(), n = grid[0].size();
p.resize(m * n + 1);
size.resize(m * n + 1);
for (int i = 0; i < p.size(); ++i) {
p[i] = i;
size[i] = 1;
}
vector<vector<int>> g(m, vector<int>(n));
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
g[i][j] = grid[i][j];
for (auto& h : hits) g[h[0]][h[1]] = 0;
for (int j = 0; j < n; ++j)
if (g[0][j] == 1)
merge(j, m * n);
for (int i = 1; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (g[i][j] == 0) continue;
if (g[i - 1][j] == 1) merge(i * n + j, (i - 1) * n + j);
if (j > 0 && g[i][j - 1] == 1) merge(i * n + j, i * n + j - 1);
}
}
vector<int> ans(hits.size());
vector<int> dirs = {-1, 0, 1, 0, -1};
for (int k = hits.size() - 1; k >= 0; --k) {
int i = hits[k][0], j = hits[k][1];
if (grid[i][j] == 0) continue;
g[i][j] = 1;
int prev = size[find(m * n)];
if (i == 0) merge(j, m * n);
for (int l = 0; l < 4; ++l) {
int x = i + dirs[l], y = j + dirs[l + 1];
if (x >= 0 && x < m && y >= 0 && y < n && g[x][y] == 1)
merge(i * n + j, x * n + y);
}
int curr = size[find(m * n)];
ans[k] = max(0, curr - prev - 1);
}
return ans;
}
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void merge(int a, int b) {
int pa = find(a), pb = find(b);
if (pa != pb) {
size[pb] += size[pa];
p[pa] = pb;
}
}
};
func hitBricks(grid [][]int, hits [][]int) []int {
m, n := len(grid), len(grid[0])
p := make([]int, m*n+1)
size := make([]int, len(p))
for i := range p {
p[i] = i
size[i] = 1
}
var find func(x int) int
find = func(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
union := func(a, b int) {
pa, pb := find(a), find(b)
if pa != pb {
size[pb] += size[pa]
p[pa] = pb
}
}
g := make([][]int, m)
for i := range g {
g[i] = make([]int, n)
for j := range g[i] {
g[i][j] = grid[i][j]
}
}
for _, h := range hits {
g[h[0]][h[1]] = 0
}
for j, v := range g[0] {
if v == 1 {
union(j, m*n)
}
}
for i := 1; i < m; i++ {
for j := 0; j < n; j++ {
if g[i][j] == 0 {
continue
}
if g[i-1][j] == 1 {
union(i*n+j, (i-1)*n+j)
}
if j > 0 && g[i][j-1] == 1 {
union(i*n+j, i*n+j-1)
}
}
}
ans := make([]int, len(hits))
dirs := []int{-1, 0, 1, 0, -1}
for k := len(hits) - 1; k >= 0; k-- {
i, j := hits[k][0], hits[k][1]
if grid[i][j] == 0 {
continue
}
g[i][j] = 1
prev := size[find(m*n)]
if i == 0 {
union(j, m*n)
}
for l := 0; l < 4; l++ {
x, y := i+dirs[l], j+dirs[l+1]
if x >= 0 && x < m && y >= 0 && y < n && g[x][y] == 1 {
union(i*n+j, x*n+y)
}
}
curr := size[find(m*n)]
ans[k] = max(0, curr-prev-1)
}
return ans
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。