algorithm - 把正方形分成小正方形

Question

我有一个大广场。我想把这个正方形分成小正方形。我需要所有可能的组合。我知道有无数种组合，但我有一个限制。我有最小正方形的固定尺寸。

我可以使用蛮力来实现它。但是太长了。

这个任务有什么更好的算法吗？

谢谢!

Answer 1

这个问题只有在我们做出 2 个假设时才有解(否则会有无限组合)

1) 最小的正方形有固定大小
2)大方 block 的切割方式也是固定的，就好像把方 block 放到一个格子里，每条线之间的距离就是小方 block 的大小。

还有第三个假设可以使问题更容易一些

3) 大正方形的边长是小正方形的 K 倍。 K为整数。

如果两个假设都成立，我们可以继续:

找出 N(N 为整数)个最小正方形的数量:大小为 N*small-size 的正方形

 if ((big-size % N*small-size)==0)
    Number += (big-size / N*small-size)^2
 else
    Number += ((big-size / N*small-size)^2) * (big-size % N*small-size)

else 条件中的 * (big-size % Nsmall-size) 是因为如果 bigsquare 没有除以 N，当“网格化”gid-width 为 N 的大正方形时，我们将留下一个“小数部分”。这样我们就可以再次开始分割(再次网格化)但偏移量为 1、2 或 N 小步。步数为(big-size % Nsmall-size)。

同样，只有在采用 3 个假设的情况下，这些步骤才成立。