题解：AT_xmascon19_f Stamps 1

cly378 · 2026-10-21 19:35:57 · 题解

题意

这道题给定一个 H \times W 的偶数边长网格，部分网格已经被涂黑，我们每次可以放置一个尺寸为 (\frac{H}{2}) \times (\frac{W}{2}) 的印章，将印章覆盖的整片矩形区域全部涂黑，目的是用最少的盖章次数，把整个网格的所有格子都涂成全黑。

解题思路

先统计当前掩码选中的印章总数。

如果当前选中的印章数已经大于我们当前记录的最小答案，可以直接跳过。

遍历所有预先收集好的空白格子，判断每个空白格子是否至少都被当前选中的随便一个印章覆盖。

如果所有空白格子都能被覆盖，就用当前的印章次数更新全局的最小答案。