c - 找出可以形成的正方形数

Question

我遇到过这个问题:

"Consider a network of NxN points with integer coordinates. Some network nodes are white, some are black (the black dots will be "1" and the white dots "0"). Using network's points with the same color as corners, may be formed squares.

For a given configuration, find the number of squares that can be formed having as vertices network's points with the same number."

例如:

4 (N)

0 1 0 0

0 0 1 1

1 0 0 0

0 1 1 1

它可以只形成一个正方形。输出将为“1”。

我该如何解决这个问题？显然，对于大多数情况，蛮力会失败，所以我认为没有必要在这里发布代码。

更新:我忘了指定

N<=50

Answer 1

我将尝试给你一个算法，你希望它能变成实际的 C 代码。一种蛮力方法可能是这样做:

1. 对于集合中的每个点，选择集合中的另一个点。
2. 根据生成的线，确定正方形中的下一条垂直线是什么，并检查集合中是否存在与所需点相匹配的点。
3. 如果找到第三个点(以及第二条边)，则对正方形的第三条边重复步骤 2。
4. 最后，如果找到三个有效点，则查看第三个点是否正确连接回原始点。如果是，那么您就有了匹配项。
5. 如果在这些步骤中有任何一个失败，则丢弃第一个点作为候选点，并返回到步骤 1，选择另一个点。遍历所有点后，您将找到一个正方形，或者确定不存在正方形。

更新和改进:

1. 对于集合中的每个点，与集合中的每个其他点进行比较，寻找与其他点垂直的两条对角线。如果找到，存储它所连接的两个点的 ID。如果未找到，则从您的集合中永久丢弃该点。这一步将是O(N^2)，但我看不出有什么办法可以避免它。

2. 接下来，遍历“选择的”点(即具有一个或多个半正方形的点)，并检查它们连接的点也自身连接回另一个选择点。如果是这样，那么您就找到了一个正方形。这里的诀窍是你不要在这里做更多的计算。您只需迭代已有的状态，这应该比第一步中的计算快得多。

这种方法比蛮力法更胜一筹，因为它只需要计算半个方 block 。计算平方蛮力是 O(N^4) 的事情。这种方法是 O(N^2)，但在实践中可能会更快，因为点集会随着算法的进行而缩小。