寻找不重叠的方块？

Question

这类问题对我来说真的很难搞清楚。我有一个网格形式的图表，如下所示。

  A-----B-----C-----D
  |     |     |     |
  E-----F-----G-----H
  |     |     |     |
  I-----J-----K-----L
  |     |     |     |
  M-----N-----O-----P

现在，这是一个有效的图表，如果我被问到有多少个方块，我应该数单位方块并回答 9。

  A-----B-----C-----D
  |     |           |
  E-----F     G     H
  |                 |
  I     J     K     L
  |                 |
  M-----N-----O-----P

这是一张无效图表，因为它包含一个 1x1 正方形与一个 3x3 正方形重叠。在这种情况下，它在一个角处重叠，但通常可以是 FGJK 或 BFJKLHDC。那些也是无效的。

我的问题是，如何验证图形是否具有不重叠的正方形，接下来，如何计算有效图形中的正方形？

此外，没有悬边，每条边都必须是正方形的一部分。

到目前为止我的方法： 1. 寻找具有给定边的最大可能正方形。尺码 M 2. 寻找具有给定边的最小可能正方形。尺码 N。 3. 检查 N 是否是 M 的因数并检查 M 方格是否与 N 方格完全平铺。

我卡住的区域：我无法使用动态编程创建算法。我创建的算法是 O(n^6) ，我在这里 post 太惭愧了。

应用领域：物体共振。请不要问原来的问题，因为我无权谈论它。

Answer 1

My question is, how can I validate the graph for being with non overlapping squares and next, how do I count the squares in a valid graph?

我是这样理解的：

检查图形是否有正方形分区
如果是，统计分区中的方格数

设n为网格边的顶点数。在你的情况下（n = 4），正好有 3 个有效配置（最多对称）：

A-----B-----C-----D        A-----B-----C-----D        A-----B-----C-----D
|     |     |     |        |     |     |     |        |                 |
E-----F-----G-----H        E-----F-----G-----H        E     F     G     H
|     |     |     |        |     |           |        |                 |
I-----J-----K-----L        I-----J     K     L        I     J     K     L
|     |     |     |        |     |           |        |                 |
M-----N-----O-----P        M-----N-----O-----P        M-----N-----O-----P

对于第一个问题，我建议的方法如下：首先，像这样为每个图块分配一个数字：

A-----B-----C-----D
|  1  |  2  |  3  |
E-----F-----G-----H
|  4  |  5  |  6  |
I-----J-----K-----L
|  7  |  8  |  9  | 
M-----N-----O-----P

然后创建属于同一分区的图块集。例如，在第二种配置中（边 2 有一个方块，边 1 有 5 个方块），您将有以下 6 个集合：{1}, {2}, {3}, {4}, {5, 6, 8, 9}, {7}。现在是验证：

自动验证大小 1 的集合
对于某些 k

4

{k}, {k+1}, {k+n-1}, {k+n}

更一般地说，对于某些 k

S^2

{ k+i+(n-1)j | 0<=i<S, 0<=j<S }

这个验证步骤实际上可以在您解析图块时完成，并在处理时标记它们：下一个未标记的图块 k 必须是正方形的左上角：检查连接到 k 的图块形成一个集合，如上述验证标准所述（通过查找连续图块之间是否存在边来检查图块连接）。这样，如果你发现一个分区不是正方形，那么你可以中止程序。

如果所有分区都经过验证，则方块数就是您找到的集合数（在本例中为 6）。

最后一件事是 "dangling edge" 问题：只需检查所有顶点的度数至少 2。这可以在算法开始时完成，也可能没有必要，具体取决于您编写 "square validation" 过程的方式。

这个程序的整体时间复杂度看起来是O(n^2)，其中n是你的网格的边，所以它实际上是按图的顺序（顶点数）线性排列的.当你提到 O(n^6) 的复杂性时，我不确定 n 是什么。

寻找不重叠的方块？

Finding non overlapping squares?

graph-theory