自动搬运

查看原文

来自洛谷，原作者为

	hanxiaofensheng AFOed. || 「愿此行 终抵群星」 || 互关私信，不活跃的可能清

搬运于2025-08-24 21:18:42，当前版本为作者最后更新于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)$。

代码