class Solution {
public:
vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
}
};
803. 打砖块
有一个 m x n 的二元网格 grid ，其中 1 表示砖块，0 表示空白。砖块 稳定（不会掉落）的前提是：
给你一个数组 hits ，这是需要依次消除砖块的位置。每当消除 hits[i] = (rowi, coli) 位置上的砖块时，对应位置的砖块（若存在）会消失，然后其他的砖块可能因为这一消除操作而 掉落 。一旦砖块掉落，它会 立即 从网格 grid 中消失（即，它不会落在其他稳定的砖块上）。
返回一个数组 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.lengthn == grid[i].length1 <= m, n <= 200grid[i][j] 为 0 或 11 <= hits.length <= 4 * 104hits[i].length == 20 <= xi <= m - 10 <= yi <= n - 1(xi, yi) 互不相同原站题解
python3 解法, 执行用时: 268 ms, 内存消耗: 23.3 MB, 提交时间: 2023-09-23 00:22:47
class Solution:
def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:
m, n = len(grid), len(grid[0])
ans = [-1]*len(hits)
def dfs(x, y):
if 0 <= x < m and 0 <= y < n and grid[x][y] == 1:
grid[x][y] = 2
ans = 1 + dfs(x + 1, y) + dfs(x - 1, y) + dfs(x, y + 1) + dfs(x, y - 1)
return ans
return 0
def is_stable(x, y):
if x == 0: return True
if x + 1 < m and grid[x + 1][y] == 2: return True
if x - 1 >= 0 and grid[x - 1][y] == 2: return True
if y + 1 < n and grid[x][y + 1] == 2: return True
if y - 1 >= 0 and grid[x][y - 1] == 2: return True
return False
# 模拟最终的残局
for x, y in hits:
grid[x][y] -= 1
# 标记稳定砖块。 注意不标记被打掉的砖块，因此这一步需要在“模拟最终的残局”之后
for y in range(n):
dfs(0, y)
# 倒推
for i in range(len(hits) - 1, -1,-1):
x, y = hits[i]
grid[x][y] += 1
# 如果不稳定，打掉也没啥影响
if not is_stable(x, y) or grid[x][y] == 0:
ans[i] = 0
else:
# 否则 dfs 计算联通图大小，这里的联通指的是值为 1。
# 实际指的是添加了 (x,y) 砖块之后，这些值为 1 的砖块会变成稳定砖块（我们用 2 表示）
# 由于我们是反推，因此就是移除 (x, y) 砖块之后， 这些稳定的砖块会变成不稳定（掉落）
ans[i] = dfs(x, y) - 1
return ans
python3 解法, 执行用时: 1000 ms, 内存消耗: 25.1 MB, 提交时间: 2023-09-23 00:22:31
class UnionFind:
def __init__(self):
self.father = {}
self.size_of_set = {}
def get_size_of_set(self,x):
"""
获取所在连通块的大小
"""
return self.size_of_set[self.find(x)]
def find(self,x):
root = x
while self.father[root] != None:
root = self.father[root]
# 路径压缩
while x != root:
original_father = self.father[x]
self.father[x] = root
x = original_father
return root
def is_connected(self,x,y):
return self.find(x) == self.find(y)
def merge(self,x,y):
root_x,root_y = self.find(x),self.find(y)
if root_x != root_y:
self.father[root_x] = root_y
# 更新根节点连通块数量
self.size_of_set[root_y] += self.size_of_set[root_x]
del self.size_of_set[root_x]
def add(self,x):
if x not in self.father:
self.father[x] = None
self.size_of_set[x] = 1
class Solution:
def __init__(self):
self.CEILING = (-1,-1)
self.DIRECTION = ((1,0),(-1,0),(0,1),(0,-1))
def initialize(self,uf,m,n,grid,hits):
"""
初始化
"""
# 添加天花板
uf.add(self.CEILING)
# 敲掉所有要敲掉的砖块
for x,y in hits:
grid[x][y] -= 1
# 连接，合并剩余的砖块
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
uf.add((i,j))
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
self.merge_neighbors(uf,m,n,grid,i,j)
# 与天花板合并
for j in range(n):
if grid[0][j] == 1:
uf.merge((0,j),self.CEILING)
def is_valid(self,x,y,grid,m,n):
return 0 <= x < m and 0 <= y < n and grid[x][y] == 1
def merge_neighbors(self,uf,m,n,grid,x,y):
"""
与上下左右的砖块合并
"""
for dx,dy in self.DIRECTION:
nx,ny = x+dx,y+dy
if not self.is_valid(nx,ny,grid,m,n):
continue
uf.merge((x,y),(nx,ny))
def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:
uf = UnionFind()
m,n = len(grid),len(grid[0])
res = [0] * len(hits)
# 初始化
self.initialize(uf,m,n,grid,hits)
for i in range(len(hits)-1,-1,-1):
x,y = hits[i][0],hits[i][1]
# 还原敲击
grid[x][y] += 1
# 敲的地方原本就不是砖块
if grid[x][y] != 1:
continue
# 敲完以后与天花板连接的数量
after_hit = uf.get_size_of_set(self.CEILING)
# 填回砖块，合并
uf.add((x,y))
self.merge_neighbors(uf,m,n,grid,x,y)
if x == 0:
uf.merge((x,y),self.CEILING)
# 被敲的地方和天花板连接
if uf.is_connected((x,y),self.CEILING):
# 敲之前和天花板连接的数量
before_hit = uf.get_size_of_set(self.CEILING)
res[i] = before_hit - after_hit - 1
return res
javascript 解法, 执行用时: 1080 ms, 内存消耗: 67.3 MB, 提交时间: 2023-09-23 00:22:13
/**
* @param {number[][]} grid
* @param {number[][]} hits
* @return {number[]}
*/
var hitBricks = function(grid, hits) {
const h = grid.length; w = grid[0].length;
const uf = new UnionFind(h * w + 1);
const status = JSON.parse(JSON.stringify(grid));;
for (let i = 0; i < hits.length; i++) {
status[hits[i][0]][hits[i][1]] = 0;
}
for (let i = 0; i < h; i++) {
for (let j = 0; j < w; j++) {
if (status[i][j] === 1) {
if (i === 0) {
uf.merge(h * w, i * w + j);
}
if (i > 0 && status[i - 1][j] === 1) {
uf.merge(i * w + j, (i - 1) * w + j);
}
if (j > 0 && status[i][j - 1] === 1) {
uf.merge(i * w + j, i * w + j - 1);
}
}
}
}
const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
const ret = new Array(hits.length).fill(0);
for (let i = hits.length - 1; i >= 0; i--) {
const r = hits[i][0], c = hits[i][1];
if (grid[r][c] === 0) {
console.log(1)
continue;
}
const prev = uf.size(h * w);
if (r === 0) {
console.log(2)
uf.merge(c, h * w);
}
for (const [dr, dc] of directions) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < h && nc >= 0 && nc < w) {
if (status[nr][nc] === 1) {
console.log(3)
uf.merge(r * w + c, nr * w + nc);
}
}
}
const size = uf.size(h * w);
ret[i] = Math.max(0, size - prev - 1);
status[r][c] = 1;
}
return ret;
};
class UnionFind {
constructor (n) {
this.f = new Array(n).fill(0).map((element, index) => index);
this.sz = new Array(n).fill(1);
}
find (x) {
if (this.f[x] === x) {
return x;
}
const newf = this.find(this.f[x]);
this.f[x] = newf;
return this.f[x];
}
merge (x, y) {
const fx = this.find(x), fy = this.find(y);
if (fx === fy) {
return;
}
this.f[fx] = fy;
this.sz[fy] += this.sz[fx];
}
size (x) {
return this.sz[this.find(x)];
}
}
golang 解法, 执行用时: 220 ms, 内存消耗: 10.7 MB, 提交时间: 2023-09-23 00:21:55
func hitBricks(grid [][]int, hits [][]int) []int {
h, w := len(grid), len(grid[0])
fa := make([]int, h*w+1)
size := make([]int, h*w+1)
for i := range fa {
fa[i] = i
size[i] = 1
}
var find func(int) int
find = func(x int) int {
if fa[x] != x {
fa[x] = find(fa[x])
}
return fa[x]
}
union := func(from, to int) {
from, to = find(from), find(to)
if from != to {
size[to] += size[from]
fa[from] = to
}
}
status := make([][]int, h)
for i, row := range grid {
status[i] = append([]int(nil), row...)
}
// 遍历 hits 得到最终状态
for _, p := range hits {
status[p[0]][p[1]] = 0
}
// 根据最终状态建立并查集
root := h * w
for i, row := range status {
for j, v := range row {
if v == 0 {
continue
}
if i == 0 {
union(i*w+j, root)
}
if i > 0 && status[i-1][j] == 1 {
union(i*w+j, (i-1)*w+j)
}
if j > 0 && status[i][j-1] == 1 {
union(i*w+j, i*w+j-1)
}
}
}
type pair struct{ x, y int }
directions := []pair{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} // 上下左右
ans := make([]int, len(hits))
for i := len(hits) - 1; i >= 0; i-- {
p := hits[i]
r, c := p[0], p[1]
if grid[r][c] == 0 {
continue
}
preSize := size[find(root)]
if r == 0 {
union(c, root)
}
for _, d := range directions {
if newR, newC := r+d.x, c+d.y; 0 <= newR && newR < h && 0 <= newC && newC < w && status[newR][newC] == 1 {
union(r*w+c, newR*w+newC)
}
}
curSize := size[find(root)]
if cnt := curSize - preSize - 1; cnt > 0 {
ans[i] = cnt
}
status[r][c] = 1
}
return ans
}
cpp 解法, 执行用时: 276 ms, 内存消耗: 107.6 MB, 提交时间: 2023-09-23 00:21:41
class UnionFind {
private:
vector<int> f, sz;
public:
UnionFind(int n): f(n), sz(n) {
for (int i = 0; i < n; i++) {
f[i] = i;
sz[i] = 1;
}
}
int find(int x) {
if (f[x] == x) {
return x;
}
int newf = find(f[x]);
f[x] = newf;
return f[x];
}
void merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy) {
return;
}
f[fx] = fy;
sz[fy] += sz[fx];
}
int size(int x) {
return sz[find(x)];
}
};
class Solution {
public:
vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
int h = grid.size(), w = grid[0].size();
UnionFind uf(h * w + 1);
vector<vector<int>> status = grid;
for (int i = 0; i < hits.size(); 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) {
uf.merge(h * w, i * w + j);
}
if (i > 0 && status[i - 1][j] == 1) {
uf.merge(i * w + j, (i - 1) * w + j);
}
if (j > 0 && status[i][j - 1] == 1) {
uf.merge(i * w + j, i * w + j - 1);
}
}
}
}
const vector<pair<int, int>> directions{{0, 1},{1, 0},{0, -1},{-1, 0}};
vector<int> ret(hits.size(), 0);
for (int i = hits.size() - 1; i >= 0; i--) {
int r = hits[i][0], c = hits[i][1];
if (grid[r][c] == 0) {
continue;
}
int prev = uf.size(h * w);
if (r == 0) {
uf.merge(c, h * w);
}
for (const auto [dr, dc]: directions) {
int nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < h && nc >= 0 && nc < w) {
if (status[nr][nc] == 1) {
uf.merge(r * w + c, nr * w + nc);
}
}
}
int size = uf.size(h * w);
ret[i] = max(0, size - prev - 1);
status[r][c] = 1;
}
return ret;
}
};
java 解法, 执行用时: 19 ms, 内存消耗: 53 MB, 提交时间: 2023-09-23 00:21:27
class Solution {
public int[] hitBricks(int[][] grid, int[][] hits) {
int h = grid.length, w = grid[0].length;
UnionFind uf = new UnionFind(h * w + 1);
int[][] status = new int[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 < hits.length; 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) {
uf.merge(h * w, i * w + j);
}
if (i > 0 && status[i - 1][j] == 1) {
uf.merge(i * w + j, (i - 1) * w + j);
}
if (j > 0 && status[i][j - 1] == 1) {
uf.merge(i * w + j, i * w + j - 1);
}
}
}
}
int[][] directions = {{0, 1},{1, 0},{0, -1},{-1, 0}};
int[] ret = new int[hits.length];
for (int i = hits.length - 1; i >= 0; i--) {
int r = hits[i][0], c = hits[i][1];
if (grid[r][c] == 0) {
continue;
}
int prev = uf.size(h * w);
if (r == 0) {
uf.merge(c, h * w);
}
for (int[] direction : directions) {
int dr = direction[0], dc = direction[1];
int nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < h && nc >= 0 && nc < w) {
if (status[nr][nc] == 1) {
uf.merge(r * w + c, nr * w + nc);
}
}
}
int size = uf.size(h * w);
ret[i] = Math.max(0, size - prev - 1);
status[r][c] = 1;
}
return ret;
}
}
class UnionFind {
int[] f;
int[] sz;
public UnionFind(int n) {
f = new int[n];
sz = new int[n];
for (int i = 0; i < n; i++) {
f[i] = i;
sz[i] = 1;
}
}
public int find(int x) {
if (f[x] == x) {
return x;
}
int newf = find(f[x]);
f[x] = newf;
return f[x];
}
public void merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy) {
return;
}
f[fx] = fy;
sz[fy] += sz[fx];
}
public int size(int x) {
return sz[find(x)];
}
}
java 解法, 执行用时: 17 ms, 内存消耗: 53.5 MB, 提交时间: 2023-09-23 00:21:02
public class Solution {
private int rows;
private int cols;
public static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
public int[] hitBricks(int[][] grid, int[][] hits) {
this.rows = grid.length;
this.cols = grid[0].length;
// 第 1 步：把 grid 中的砖头全部击碎，通常算法问题不能修改输入数据，这一步非必需，可以认为是一种答题规范
int[][] copy = new int[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
copy[i][j] = grid[i][j];
}
}
// 把 copy 中的砖头全部击碎
for (int[] hit : hits) {
copy[hit[0]][hit[1]] = 0;
}
// 第 2 步：建图，把砖块和砖块的连接关系输入并查集，size 表示二维网格的大小，也表示虚拟的「屋顶」在并查集中的编号
int size = rows * cols;
UnionFind unionFind = new UnionFind(size + 1);
// 将下标为 0 的这一行的砖块与「屋顶」相连
for (int j = 0; j < cols; j++) {
if (copy[0][j] == 1) {
unionFind.union(j, size);
}
}
// 其余网格，如果是砖块向上、向左看一下，如果也是砖块，在并查集中进行合并
for (int i = 1; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (copy[i][j] == 1) {
// 如果上方也是砖块
if (copy[i - 1][j] == 1) {
unionFind.union(getIndex(i - 1, j), getIndex(i, j));
}
// 如果左边也是砖块
if (j > 0 && copy[i][j - 1] == 1) {
unionFind.union(getIndex(i, j - 1), getIndex(i, j));
}
}
}
}
// 第 3 步：按照 hits 的逆序，在 copy 中补回砖块，把每一次因为补回砖块而与屋顶相连的砖块的增量记录到 res 数组中
int hitsLen = hits.length;
int[] res = new int[hitsLen];
for (int i = hitsLen - 1; i >= 0; i--) {
int x = hits[i][0];
int y = hits[i][1];
// 注意：这里不能用 copy，语义上表示，如果原来在 grid 中，这一块是空白，这一步不会产生任何砖块掉落
// 逆向补回的时候，与屋顶相连的砖块数量也肯定不会增加
if (grid[x][y] == 0) {
continue;
}
// 补回之前与屋顶相连的砖块数
int origin = unionFind.getSize(size);
// 注意：如果补回的这个结点在第 1 行，要告诉并查集它与屋顶相连（逻辑同第 2 步）
if (x == 0) {
unionFind.union(y, size);
}
// 在 4 个方向上看一下，如果相邻的 4 个方向有砖块，合并它们
for (int[] direction : DIRECTIONS) {
int newX = x + direction[0];
int newY = y + direction[1];
if (inArea(newX, newY) && copy[newX][newY] == 1) {
unionFind.union(getIndex(x, y), getIndex(newX, newY));
}
}
// 补回之后与屋顶相连的砖块数
int current = unionFind.getSize(size);
// 减去的 1 是逆向补回的砖块（正向移除的砖块），与 0 比较大小，是因为存在一种情况，添加当前砖块，不会使得与屋顶连接的砖块数更多
res[i] = Math.max(0, current - origin - 1);
// 真正补上这个砖块
copy[x][y] = 1;
}
return res;
}
/**
* 输入坐标在二维网格中是否越界
*
* @param x
* @param y
* @return
*/
private boolean inArea(int x, int y) {
return x >= 0 && x < rows && y >= 0 && y < cols;
}
/**
* 二维坐标转换为一维坐标
*
* @param x
* @param y
* @return
*/
private int getIndex(int x, int y) {
return x * cols + y;
}
private class UnionFind {
/**
* 当前结点的父亲结点
*/
private int[] parent;
/**
* 以当前结点为根结点的子树的结点总数
*/
private int[] size;
public UnionFind(int n) {
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
/**
* 路径压缩，只要求每个不相交集合的「根结点」的子树包含的结点总数数值正确即可，因此在路径压缩的过程中不用维护数组 size
*
* @param x
* @return
*/
public int find(int x) {
if (x != parent[x]) {
parent[x] = find(parent[x]);
}
return parent[x];
}
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) {
return;
}
parent[rootX] = rootY;
// 在合并的时候维护数组 size
size[rootY] += size[rootX];
}
/**
* @param x
* @return x 在并查集的根结点的子树包含的结点总数
*/
public int getSize(int x) {
int root = find(x);
return size[root];
}
}
}