彩色盒子按约束分组为正方形的算法求解问题

假设存在一个大小为 width * height 的二维数组，数组的每个元素对应一个彩色盒子。
盒子总数量为 n，所有盒子的颜色总数为常数 c，且满足 c <<< n。
现给定参数 k，需设计算法将所有盒子分组为多个正方形块，需满足以下约束：

• 每个分组包含的盒子数量必须是完全平方数（如1、4、9、16、25、36……），可构成正方形
• 同一个分组内的所有盒子颜色必须完全相同，单元素正方形为合法分组
• 所有正方形分组不可重叠
  最终要使得分组总数量尽可能接近 k。

核心逻辑是先得到边界分组数，再根据目标k的位置做定向调整，时间复杂度仅和二维数组大小正相关，适配c <<< n的前置条件。

前置预处理步骤 #

• 计算每个坐标的最大同色正方形边长
  用动态规划实现：定义dp[i][j]表示以坐标(i,j)为右下角的最大同色正方形边长，递推规则如下：
  1. 边界坐标（第一行/第一列）的dp[i][j]默认值为1
  2. 若grid[i][j]与上方、左方、左上方三个坐标的像素颜色完全相同，则dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1，否则dp[i][j] = 1
• 计算边界分组数
  • 最小分组数min_k：优先取最大的可用同色正方形做全局覆盖，得到最少的分组数量
  • 最大分组数max_k：所有盒子都拆为1*1的单元素正方形，值为n = width * height

定向调整逻辑 #

根据目标k和两个边界值的关系，直接选择对应方案：

1. 若k >= max_k：直接返回全单元素正方形的分组方案，此时分组数等于max_k，是最接近k的合法结果
2. 若k <= min_k：直接返回最小分组的覆盖方案，此时分组数等于min_k，是最接近k的合法结果
3. 若min_k < k < max_k：通过拆分大正方形逐步增加分组数，直到接近k
   • 先将当前所有已划分的正方形按边长从大到小排序
   • 计算当前分组数和目标k的差值delta = k - current_cnt
   • 每次取当前最大的正方形做拆分：边长为s的正方形完整拆分可新增s² - 1个分组，可根据剩余delta的大小选择拆分粒度，比如只拆分部分区域得到刚好匹配剩余delta的增量
   • 重复上述操作直到delta归零，或无更多可拆分的正方形为止

优化点 #

由于颜色总数c是远小于n的常数，可以按颜色单独划分连通域，每个连通域独立做正方形划分和调整，能进一步降低计算复杂度。

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