我有一些由8x8正方形构成的图形。我需要使用尽可能少的8x8、16x16、32x32和64x64大小的正方形来铺设它们。四个排列成正方形的8x8正方形可以被一个16x16的正方形替代,例如:
有什么算法可以实现这个目标?
有什么算法可以实现这个目标?
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]
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])