1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
class UnionFind:
def __init__(self, n):
self.parent = [i for i in range(n)]
self.size = [1 for _ in range(n)]
def find(self, x):
while x != self.parent[x]:
self.parent[x] = self.parent[self.parent[x]]
x = self.parent[x]
return x
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False
self.parent[root_x] = root_y
self.size[root_y] += self.size[root_x]
return True
def is_connected(self, x, y):
return self.find(x) == self.find(y)
def get_size(self, x):
root_x = self.find(x)
return self.size[root_x]
class Solution:
def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:
directions = {(0, 1), (1, 0), (-1, 0), (0, -1)}
rows, cols = len(grid), len(grid[0])
def is_area(x, y):
return 0 <= x < rows and 0 <= y < cols
def get_index(x, y):
return x * cols + y
copy_grid = [[grid[i][j] for j in range(cols)] for i in range(rows)]
for hit in hits:
copy_grid[hit[0]][hit[1]] = 0
union_find = UnionFind(rows * cols + 1)
for j in range(cols):
if copy_grid[0][j] == 1:
union_find.union(j, rows * cols)
for i in range(1, rows):
for j in range(cols):
if copy_grid[i][j] == 1:
if copy_grid[i - 1][j] == 1:
union_find.union(get_index(i - 1, j), get_index(i, j))
if j > 0 and copy_grid[i][j - 1] == 1:
union_find.union(get_index(i, j - 1), get_index(i, j))
size_hits = len(hits)
res = [0 for _ in range(size_hits)]
for i in range(size_hits - 1, -1, -1):
x, y = hits[i][0], hits[i][1]
if grid[x][y] == 0:
continue
origin = union_find.get_size(rows * cols)
if x == 0:
union_find.union(y, rows * cols)
for direction in directions:
new_x = x + direction[0]
new_y = y + direction[1]
if is_area(new_x, new_y) and copy_grid[new_x][new_y] == 1:
union_find.union(get_index(x, y), get_index(new_x, new_y))
curr = union_find.get_size(rows * cols)
res[i] = max(0, curr - origin - 1)
copy_grid[x][y] = 1
return res
|