使用不同大小的正方形，寻找最佳平铺策略

Question

我有一些由8x8正方形构成的图形。我需要使用尽可能少的8x8、16x16、32x32和64x64大小的正方形来铺设它们。四个排列成正方形的8x8正方形可以被一个16x16的正方形替代，例如：

有什么算法可以实现这个目标？

- Simononon

Answer 1

这需要使用动态规划算法来解决。我们假设有一个布尔类型的square[r][c]数组，如果(r, c)有一个1x1的正方形，则为true（我简化了解决方案，使其适用于1x1、2x2、4x4和8x8的正方形，以便更容易理解，但很容易适应其他大小）。在顶部行和左侧列上用false的哨兵值填充它。

定义一个二维的count数组，其中count[r][c]表示位于(r, c)上方和左侧区域中的1x1正方形数量。我们可以使用dp算法将它们相加：

count[0..n][0..m] = 0
for i in 1..n:
  for j in 1..m:
    count[i][j] = count[i-1][j] + count[i][j-1] -
        count[i-1][j-1] + square[i][j]

以上内容的实现方法是将我们已经知道总和的两个区域相加，减去重复计算的面积，并添加新单元格。使用count数组，我们可以在常量时间内使用类似的方法测试一个正方形区域是否完全被1x1的正方形覆盖。

// p1 is the top-left coordinate, p2 the bottom-right
function region_count(p1, p2):
  return count[p1.r][p1.c] - count[p1.r][p2.c-1] -
      count[p2.r-1][p1.c] + 2*count[p2.r-1][p2.c-1]

我们接着创建了第二个2D的min_squares数组，其中min_squares[r][c]代表覆盖原始1x1正方形所需的最小正方形数量。这些值可以通过另一个动态规划算法计算得出：

min_squares = count
for i in 1..n:
  for j in 1..m:
    for size in [2, 4, 8]:
      if i >= size and j >= size and
          region_count((i-size, j-size), (i, j)) == size*size:
        min_squares[i][j] = min(min_squares[i][j],
            min_squares[i-size-1][j] +
            min_squares[i][j-size-1] -
            min_squares[i-size-1][j-size-1] +
            1)

为了重构所需的平铺以获得计算出的最小值，我们使用一个辅助的size_used[r][c]数组来跟踪放置在(r, c)处正方形的大小。从这里，我们可以递归地重构平铺：

function reconstruct(i, j):
  if i < 0 or j < 0:
    return
  place square of size size_used[i][j] at (i-size_used[i][j]+1, j-size_used[i][j]+1)
  reconstruct(i-size_used[i][j], j)
  reconstruct(i, j-size_used[i][j])

- moinudin

Answer 2

你可能想看一下将基于形状的单元格划分为最少数量的矩形的最佳方法 - 如果我理解正确，这是相同的问题，但是针对的是矩形而不是正方形。

- Shadikka