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
| from typing import List
class Solution:
def minimumOperations(self, grid: List[List[int]]) -> int:
rows = len(grid)
cols = len(grid[0])
count = 0
directions = [(-1,0),(1,0),(0,-1),(0,1)]
match = [[-1] * cols for _ in range(rows)]
visited = [[-1] * cols for _ in range(rows)]
def dfs(i, j, v):
for di, dj in directions:
x = i + di
y = j + dj
if 0 <= x < rows and 0 <= y < cols and grid[x][y] and visited[x][y] != v:
visited[x][y] = v
if match[x][y] == -1 or dfs(match[x][y] // cols, match[x][y] % cols, v):
match[x][y] = i * cols + j
match[i][j] = x * cols + y
return 1
return 0
for i in range(rows):
for j in range(cols):
if grid[i][j] and match[i][j] == -1:
visited[i][j] = i * cols + j
count += dfs(i, j, visited[i][j])
return count
|