N×N二进制矩阵最小代价覆盖$符号问题求解及Python代码

问题描述 #

给定N×N的二进制矩阵，元素由'-'和'$'组成。允许执行以下操作：选择M×M（1≤M≤N）的正方形子矩阵，将其中所有'$'转为'-'，操作代价为M个硬币。目标是找到覆盖所有'$'的最小代价方案。
示例矩阵：

$$---
-$$--
$-$--
-----
----$

示例输出为4，解释：左上角6个'$'用3×3正方形覆盖（代价3），右下角'$'用1×1正方形覆盖（代价1），总代价3+1=4。

解法思路 #

核心思路是贪心+动态规划预处理：

• 先通过动态规划预处理矩阵，计算每个位置作为右下角能构成的最大全'$'正方形边长。
• 从最大的正方形边长开始遍历，优先用大正方形覆盖未被处理的'$'区域——大正方形的单位覆盖成本更低（比如3×3覆盖最多9个位置仅需3硬币，远低于用9个1×1的9硬币）。
• 标记已覆盖的区域，避免重复计算，累加每次操作的代价得到最终最小总代价。

Python实现代码 #

def min_cost_cover(matrix):
    n = len(matrix)
    if n == 0:
        return 0
    
    # 预处理：计算每个位置作为右下角的最大全'$'正方形边长
    max_square = [[0]*n for _ in range(n)]
    # 初始化第一行和第一列
    for i in range(n):
        max_square[i][0] = 1 if matrix[i][0] == '$' else 0
        max_square[0][i] = 1 if matrix[0][i] == '$' else 0
    
    # 动态规划填充max_square矩阵
    for i in range(1, n):
        for j in range(1, n):
            if matrix[i][j] == '$':
                max_square[i][j] = min(max_square[i-1][j], max_square[i][j-1], max_square[i-1][j-1]) + 1
            else:
                max_square[i][j] = 0
    
    # 标记已覆盖的位置
    covered = [[False]*n for _ in range(n)]
    total_cost = 0
    
    # 从最大边长到1遍历，优先用大正方形覆盖
    for m in range(n, 0, -1):
        # 遍历所有可能的右下角位置（确保m×m正方形不越界）
        for i in range(m-1, n):
            for j in range(m-1, n):
                if max_square[i][j] >= m and not covered[i][j]:
                    # 标记当前m×m正方形内的所有位置为已覆盖
                    for x in range(i - m + 1, i + 1):
                        for y in range(j - m + 1, j + 1):
                            covered[x][y] = True
                    total_cost += m
    return total_cost

# 测试示例矩阵
sample_matrix = [
    ['$', '$', '-', '-', '-'],
    ['-', '$', '$', '-', '-'],
    ['$', '-', '$', '-', '-'],
    ['-', '-', '-', '-', '-'],
    ['-', '-', '-', '-', '$']
]

print(min_cost_cover(sample_matrix))  # 输出：4

代码说明 #

1. 预处理阶段：参考经典的最大正方形问题解法，用动态规划计算每个位置能构成的最大全'$'正方形边长，为后续贪心选择提供依据。
2. 贪心覆盖阶段：从最大的正方形边长开始，找到未被覆盖的有效正方形，标记覆盖区域并累加代价。这种策略能保证每次选择的都是当前成本效益最高的覆盖方式，最终得到最小总代价。

内容的提问来源于stack exchange，提问作者Codebeast