题解：B4335 [中山市赛 2023] 互质

Carsy · 2025-06-12 15:38:24 · 题解

题意：给一个的整数矩阵，我们需要在里面放若干个不重叠的 3×3 子矩阵，使得这些子矩阵覆盖的元素之和最大；如果没有可以放置的子矩阵，则返回 0。

思路

• 枚举所有可能的 3\times 3 子矩阵：遍历矩阵中每个可能作为 3\times 3 子矩阵左上角的位置，计算每个子矩阵的元素和。
• dfs：使用 dfs 尝试所有可能的子矩阵组合，确保选择的子矩阵互不重叠，并记录最大的和值。其中有两种选择：选或不选。如果选择当前子矩阵，需要确保它与已选的子矩阵都不重叠。在 dfs 中，如果发现当前路径的和不可能超过已记录的最大值，可以提前终止该分支的搜索。

  注意点

• 子矩阵生成：对于这个矩阵，可以生成的 3\times 3 子矩阵数量为 (n-2)\times (n-2) 个。每个子矩阵由其左上角坐标 i,j 唯一确定。
• 重叠判断条件：它们在 x 轴和 y 轴上的投影都有重叠。
• 优先选择和较大的子矩阵，这样更容易快速找到较大的和值。

  复杂度分析

  时间复杂度：O(2^k)（差一点超时/ll）。
  空间复杂度：O(k)。

代码