力扣第 2123 题
题目
给你一个 下标从 0 开始 的矩阵 grid。每次操作，你可以把 grid 中的 一个 1 变成 0 。
如果一个矩阵中，没有 1 与其它的 1 四连通（也就是说所有 1 在上下左右四个方向上不能与其他 1 相邻），那么该矩阵就是 完全独立 的。
请返回让 grid 成为 完全独立 的矩阵的 最小操作数。
示例 1:
输入: grid = [[1,1,0],[0,1,1],[1,1,1]]
输出: 3
解释: 可以进行三次操作（把 grid[0][1], grid[1][2] 和 grid[2][1] 变成 0）。
操作后的矩阵中的所有的 1 与其它 1 均不相邻，因此矩阵是完全独立的。
示例 2:
输入: grid = [[0,0,0],[0,0,0],[0,0,0]]
输出: 0
解释: 矩阵中没有 1，此时矩阵也是完全独立的，因此无需操作，返回 0。
示例 3:
输入: grid = [[0,1],[1,0]]
输出: 0
解释: 矩阵中的所有的 1 与其它 1 均不相邻，已经是完全独立的，因此无需操作，返回 0。
提示:
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j] 是 0 或者 1.
相似问题：
分析
- 相邻的 1 连边，即是二分图（按i+j的奇偶性分为两边）
- 问题转为求最小点覆盖，即是最大匹配数，可以用网络流解决
解答
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
|
class Dinic:
def __init__(self,):
self.g = defaultdict(list) # g 是图中每个 u 对应的 v 列表
self.h = {} # h 是图中每个 u 离源点 s 的距离
self.p = defaultdict(int) # p 是当前弧优化，跳过已增广的边
def add(self,u,v,c): # 顶点 u 和 v 连边，容量 c
self.g[u].append([v,len(self.g[v]),c])
self.g[v].append([u,len(self.g[u])-1,0])
def bfs(self,s,t):
self.h = {s:0}
self.p = defaultdict(int)
Q = deque([s])
while Q:
u = Q.popleft()
for v,_,c in self.g[u]:
if v not in self.h and c>0:
Q.append(v)
self.h[v]=self.h[u]+1
return t in self.h
def dfs(self,u,t,flow):
if u==t:
return flow
res = 0
for i in range(self.p[u],len(self.g[u])):
v,j,c = self.g[u][i]
if self.h[v]==self.h[u]+1 and c>0:
a = self.dfs(v,t,min(flow,c))
flow -= a
self.g[u][i][-1]-=a
self.g[v][j][-1]+=a
res += a
self.p[u] += 1
return res
def cal(self,s,t):
res = 0
while self.bfs(s,t):
res += self.dfs(s,t,inf)
return res
class Solution:
def minimumOperations(self, grid: List[List[int]]) -> int:
m,n = len(grid),len(grid[0])
dic = Dinic()
s,t = m*n,m*n+1
for i in range(m):
for j in range(n):
if grid[i][j]==1:
u = i*n+j
if (i+j)%2:
dic.add(s,u,1)
else:
dic.add(u,t,1)
for x,y in [(i-1,j),(i,j-1)]:
if 0<=x<m and 0<=y<n and grid[x][y]==1:
v = x*n+y
if (i+j)%2:
dic.add(u,v,1)
else:
dic.add(v,u,1)
return dic.cal(s,t)
|
3463 ms