龙大心情不好 心理医生建议他朝墙壁丢石头纾压
龙大真的很调皮 每丢一块就会计算有多少砖块被他砸落
龙大:哈哈，这面墙就跟边版一样被我搞崩了
路人看到调皮的龙大指责他的不是
龙大:甘你屁事@@
Python code:
class Solution:
def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) ->
List[int]:
m, n = len(grid), len(grid[0])
root = list(range(m*n+1))
group = [1]*(m*n+1)
group[m*n] = 0
def find(x):
if root[x] != x:
root[x] = find(root[x])
return root[x]
def union(a, b):
ra, rb = find(a), find(b)
if ra != rb:
root[ra] = rb
group[rb] += group[ra]
for index, (i, j) in enumerate(hits):
if grid[i][j] == 1:
grid[i][j] = 0
else:
hits[index] = [-1,-1]
for i in range(m):
for j in range(n):
if grid[i][j]:
if i != m-1 and grid[i+1][j] == 1:
union(i*n + j, (i+1)*n + j)
if j != n-1 and grid[i][j+1] == 1:
union(i*n + j, i*n + j + 1)
if i == 0:
union(i*n + j, m*n)
res = [0]*len(hits)
dx = [0,0,1,-1]
dy = [1,-1,0,0]
for i in range(len(hits)-1, -1, -1):
origin = group[find(m*n)]
if hits[i] != [-1, -1]:
x, y = hits[i]
grid[x][y] = 1
if x == 0:
union(x*n + y, m*n)
for j in range(4):
adjx, adjy = x+dx[j], y+dy[j]
if 0 <= adjx < m and 0 <= adjy < n and grid[adjx][adjy]
== 1:
union(x*n + y, adjx*n + adjy)
res[i] = group[find(m*n)] - origin - (find(x*n+y) ==
find(m*n))
else:
res[i] = 0
return res
我也忘记这题在干嘛了