解法
先把所有该消的都消掉,现在和第一行相通的点都是“稳定点”
然后把消除顺序反过来遍历一遍
当把(i,j)
恢复成1之后,它会把它四个方向上的集合连通
假如连通完毕后“稳定点”所在的那个集合的的点的个数上涨了x个(x一定大于1),说明消除(i,j)
使得有x-1
个点从“稳定点”变得不稳定了,那也就是这次消除后drop的数量
class Solution(object):
def hitBricks(self, grid, hits):
"""
:type grid: List[List[int]]
:type hits: List[List[int]]
:rtype: List[int]
"""
from collections import defaultdict
m = len(grid)
n = len(grid[0])
f = range(m*n+1)
END = m*n
sz = defaultdict(lambda:1)
for i,j in hits:
if grid[i][j]==1:
grid[i][j]=2
def find(x):
r = x
while f[r]!=r:
r = f[r]
while f[x]!=r:
tmp = f[x]
f[x] = r
x = tmp
return r
def join(x,y):
rx,ry = find(x),find(y)
if rx!=ry:
if rx<ry:
rx,ry = ry,rx
f[ry] = rx
sz[rx] += sz[ry]
for i,j in itertools.product(xrange(m),xrange(n)):
if grid[i][j]==1:
x = i*n+j
if i and grid[i-1][j]==1:
join(x-n,x)
if j and grid[i][j-1]==1:
join(x-1,x)
if i==0:
join(END,x)
# print [find(x) for x in xrange(END+1)]
prev = sz[END]
ans = []
for i,j in hits[::-1]:
# print grid
if grid[i][j]==2:
x = i*n+j
if i and grid[i-1][j]==1:join(x-n,x)
if j and grid[i][j-1]==1:join(x-1,x)
if i+1<m and grid[i+1][j]==1:join(x+n,x)
if j+1<n and grid[i][j+1]==1:join(x+1,x)
if i==0:
join(END,x)
grid[i][j] = 1
# print [find(x) for x in xrange(END+1)]
if sz[END]>prev:
ans.append(sz[END]-prev-1)
prev = sz[END]
# print prev
else:
ans.append(0)
else:
ans.append(0)
return ans[::-1]