题目重点：每个洞连接所在行和列，选行或列使所有洞被覆盖。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 矩阵0为洞、1为完整；每板覆盖一整行或一整列，板数成本均为1。
- 这里只求最少板数；若板宽/长度不能完整覆盖或允许任意短段，图模型不适用。
解题路线
- 建立二分图，行是左点、列是右点，每洞是一条边。选一块板等于选一个点，洞被补等于相应边至少一端被选。
- 这是二分图最小点覆盖。Kőnig等式给最小点覆盖大小等于最大匹配；示例用增广路径构造最大匹配，不能把“选洞最多的行”贪心当精确。
- 要实际板集合，从所有未匹配行沿未匹配边去列、匹配边回行，得到可达集合Z；答案为未达行加可达列。返回数值代码不包含集合重建。
手动走一遍
洞(0,0),(0,1),(1,1)：最大匹配两条，因此至少2板，选行0/1或列0/1均可。所有洞都在一行，最大匹配最多1，选这一行即可；无洞答案0。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def minimum_lines(holes):
graph = {}
for r,c in holes:
graph.setdefault(r,set()).add(c)
matching = {}
def augment(r,seen):
for c in graph[r]:
if c in seen:
continue
seen.add(c)
if c not in matching or augment(matching[c],seen):
matching[c] = r
return True
return False
return sum(augment(r,set()) for r in graph)
复杂度
基础增广O(R×E)最坏时间、O(R+C+E)空间；递归深度可达R，超大输入用显式栈或Hopcroft–Karp的O(E√(R+C))实现。
易错点与追问
容易失分的边界
- n×m里行板应长m、列板应长n，尺寸记号混写要先clarify。
- 一般图最小点覆盖不等于最大匹配，必须使用行列二分结构。
继续深挖
- 板成本各不相同怎样通过源→行、列→汇和大容量洞边转最小割？
- 如果一些洞必须被两板交叉覆盖，原点覆盖约束怎样变化？
