在二维图中找到最大平方的最有效算法 [英] Most efficient algorithm to find the biggest square in a two dimension map

问题描述

我想知道不同的算法，该算法可以在点缀有障碍物的二维图中找到最大的正方形。

I would like to know the different algorithms to find the biggest square in a two dimensions map dotted with obstacles.

示例，其中 o 将成为障碍：

An example, where o would be obstacles:

...........................
....o......................
............o..............
...........................
....o......................
...............o...........
...........................
......o..............o.....
..o.......o................

最大的平方数是（如果我们选择第一个）：

The biggest square would be (if we choose the first one):

.....xxxxxxx...............
....oxxxxxxx...............
.....xxxxxxxo..............
.....xxxxxxx...............
....oxxxxxxx...............
.....xxxxxxx...o...........
.....xxxxxxx...............
......o..............o.....
..o.......o................

最快的算法是什么d吗？

What would be the fastest algorithm to find it? The one with the smallest complexity?

编辑：我知道人们对公认的答案中解释的算法很感兴趣，所以我做了一个文档对其进行了进一步解释，您可以在此处找到：

I know that people are interested on the algorithm explained in the accepted answer, so I made a document that explains it a bit more, you can find it here:

https://docs.google.com/document/d/19pHCD433tYsvAor0WObxa2qusAjKdx96kaf3z5I8XT8/edit?usp=sharing

推荐答案

以下是在最适时间 O（nm）内执行此操作的方法。这是建立在@dukeling洞察力之上的，您永远不需要检查大小小于当前已知最佳解决方案的解决方案。

Here is how to do this in the optimal amount of time, O(nm). This is built on top of @dukeling's insight that you never need to check a solution of size less than your current known best solution.

关键是要能够构建可以在O（1）时间内回答此查询的数据结构。

The key is to be able to build a data structure that can answer this query in O(1) time.

• 正方形的左上角是否有障碍物？ r，c且大小为k？

要解决该问题，我们将支持在O（ 1）。

To solve that problem, we'll support answering a slightly harder question, also in O(1).

• 从r1，c1到r2，c2的矩形中的项目数是多少？

用矩形计数问题的答案很容易回答正方形存在问题。

It's easy to answer the square existence question with an answer from the rectangle count question.

要回答矩形计数问题，请注意，如果您已经预先计算了从左上角开始的每个矩形的答案，则可以通过仅使用矩形的一种巧妙/包含排除策略来回答从r1，c1到r2，c2的一般问题从左上方开始的

To answer the rectangle count question, note that if you had pre-computed the answer for every rectangle that starts in the top left, then you could answer the general question for from r1, c1 to r2, c2 by a kind of clever/inclusion exclusion tactic using only rectangles that start in the top left

              c1   c2  
-----------------------
|             |    |  |
|   A         | B  |  |
|_____________|____|  |  r1
|             |    |  |
|    C        |  D |  |
|_____________|____|  |  r2
|_____________________|

我们想要D里面的东西的数量。根据我们从左上角预先计算的数量

We want the count of stuff inside D. In terms of our pre-computed counts from the top left.

Count(D) = Count(A ∪ B ∪ C ∪ D) - Count(A ∪ C) - Count(A ∪ B) + Count(A)

您可以预先计算O中所有左上角的矩形（nm）做一些聪明的行/列部分和，但我将留给您。

You can pre-compute all the top left rectangles in O(nm) by doing some clever row/column partial sums, but I'll leave that to you.

然后回答您要解决的问题只涉及检查可能解决方案，从至少与您所知最出色的解决方案开始。您所知的最佳值最多只能达到min（n，m）倍，因此，best_possible增量将很少发生，并且几乎所有平方都将在O（1）时间内被拒绝。

Then to answer the to the problem you want just involves checking possible solutions, starting with solutions that are at least as good as your known best. Your known best will only get better up to min(n, m) times total, so the best_possible increment will happen very rarely and almost all squares will be rejected in O(1) time.

best_possible = 0
for r in range(n):
 for c in range(m):
   while True:                      
     # this looks O(min(n, m)), but it's amortized O(1) since best_possible
     # rarely increased.      
     if possible(r, c, best_possible+1):
       best_possible += 1
     else:
       break

这篇关于在二维图中找到最大平方的最有效算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！