难度: Hard
Submission
运行时间: 632 ms
内存: 66.3 MB
from typing import List
from functools import lru_cache
from collections import defaultdict, deque
class Solution:
def minimumOperations(self, grid: List[List[int]]) -> int:
"""
:param grid:
:return:
"""
m1 = defaultdict(set)
for k,v in enumerate(grid):
for k2, v2 in enumerate(v):
if v2 == 1:
if k > 0 and grid[k-1][k2] == 1:
upper_idx = (k-1)*len(grid[0])+k2
cur_idx = k*len(grid[0])+k2
m1[upper_idx].add(cur_idx)
m1[cur_idx].add(upper_idx)
if k2 > 0 and grid[k][k2-1] == 1:
left_idx = k*len(grid[0])+k2-1
cur_idx = k*len(grid[0])+k2
m1[left_idx].add(cur_idx)
m1[cur_idx].add(left_idx)
vis = set()
def match(i):
nonlocal m1, vis
for j in m1[i]:
if j not in vis:
vis.add(j)
if j not in link or match(link[j]):
link[j] = i
link[i] = j
return True
return False
link = {}
ans = 0
for i in m1:
if i not in link:
vis.clear()
if match(i):
ans += 1
return ans
Explain
这个题解使用图的最大匹配算法来解决问题。首先，将矩阵中的每个元素转换为图中的一个节点，节点的索引是通过行号和列号计算得到的。如果两个相邻的元素都是1，则在它们之间建立一条边。这样，原问题转化为找出图中的最大匹配，即最多的可以互不相邻的1对1的匹配。使用匈牙利算法（增广路径算法）来实现最大匹配。每次尝试找到一个未被匹配的节点，并尝试通过递归的方式进行匹配。如果可以匹配，增加匹配数，并递归尝试匹配更多节点。
时间复杂度: O(V(V+E))
空间复杂度: O(V+E)
from typing import List
from functools import lru_cache
from collections import defaultdict, deque
class Solution:
def minimumOperations(self, grid: List[List[int]]) -> int:
m1 = defaultdict(set)
for k,v in enumerate(grid):
for k2, v2 in enumerate(v):
if v2 == 1:
# Check and link adjacent 1s vertically
if k > 0 and grid[k-1][k2] == 1:
upper_idx = (k-1)*len(grid[0])+k2
cur_idx = k*len(grid[0])+k2
m1[upper_idx].add(cur_idx)
m1[cur_idx].add(upper_idx)
# Check and link adjacent 1s horizontally
if k2 > 0 and grid[k][k2-1] == 1:
left_idx = k*len(grid[0])+k2-1
cur_idx = k*len(grid[0])+k2
m1[left_idx].add(cur_idx)
m1[cur_idx].add(left_idx)
vis = set()
def match(i):
nonlocal m1, vis
for j in m1[i]:
if j not in vis:
vis.add(j)
if j not in link or match(link[j]):
link[j] = i
link[i] = j
return True
return False
link = {}
ans = 0
for i in m1:
if i not in link:
vis.clear()
if match(i):
ans += 1
return ans
Explore
图的最大匹配算法适用于这个问题是因为我们需要找到最大数量的互不相邻的1对来消除。这可以被视为一个典型的图匹配问题，其中每个1代表一个节点，相邻的1之间有边连接。尽管可以考虑使用动态规划或贪心算法，但这些方法在处理节点之间复杂关系的情况下通常效果不佳或难以实现。最大匹配算法提供了一个精确的方法来确定最多的不相交对，这是处理此类问题的标准方法之一。
在构建图的过程中，我通过在添加边之前检查索引的合法性来处理矩阵边界。例如，当检查一个元素的上方相邻元素是否为1时，我会先判断这个元素是否在第一行；类似地，检查左侧元素时，会判断是否在第一列。这样通过条件判断确保不会访问到矩阵之外的元素，避免了数组越界的错误。
在使用匈牙利算法进行匹配时，我通过使用递归函数和访问标记来确保过程的高效性。特别地，利用一个集合来记录已访问过的节点，以避免重复处理和陷入无限循环。每次尝试匹配前，会清空访问标记集合，保证每次搜索的独立性。此外，使用字典来存储节点间的连接关系和当前的匹配状态，使得查找和更新操作都能在常数时间内完成。这些数据结构的选择和使用大大提高了算法的效率和实现的简洁性。