Geek Answers Handbook

The most efficient algorithm for finding the largest square in a two-dimensional map

I would like to know various algorithms to find the largest square in a two-dimensional map dotted with obstacles.

An example where there owill be obstacles:

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

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

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

What will be the fastest algorithm to find it? The one that has the least difficulty?

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

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

+4
source share
5 answers

, O (). @dukeling, , .

, O (1).

  • , r, c k?

, , O (1).

  • r1, c1 r2, c2?

.

, , , , : r1, c1 r2, c2 / , ,

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

, D. .

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

O (nm), /, .

, , , , , , , , . (n, m) , best_possible , O (1) .

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

, .

:

. , 1x1.

  • , 1 .
  • , . , .

:

, .

:

, , / .

, , .

.

:

, , .

:

2 , , - , (O(min(m,n) log max(m,n))) .

, .

, m n, O(mn log m).

, , .

:

:

 012345678901234567890123456
0...........................
1....o......................
2............o..............
3...........................
4....o......................
5...............o...........
6...........................
7......o..............o.....
8..o.......o................

1x1 , .

2x2. [0,1] 1, {4} - , , . [0,1] 1, , - {}.

3x3. [0,2] 2, 1 12, {12}. [0,2] 2, 8, {8}.

4x4. [0,3] 3 - {}. [0,3] 3 - {}.

5x5. [0,4] 4 - {4}. [0,4] 4 - {1,4}.

, . [0,4] 4 , ( ). , .

4 ( - ) [0,4]. 5-8 [0,4], , , 5,0, .

, 5x5, , 6x6 7x7, .

8x8, .

.

, ?

, . . , . , .

, , .

+4

, .

Store the x-y positions of all the obstacles.
For each obstacle O
   find obstacle C that is nearest to it column-wise.
   find obstacle R-top that is nearest to it row-wise from the top.
   find obstacle R-bottom that is nearest to it row-wise from the bottom.
   if (|R-top.y - R-bottom.y| != |O.x - C.x|) continue
   Size of the square = Abs((R-top.y - R-bottom.y) * (O.x - C.x))
Keep track of the sizes and positions to find the largest square

O(k^2), k - . O(k * log k), .

+2

SO / , . , .

, , Python/.

# obstacleMap is a list of list of MapElements, stored in row-major order
max([find_largest_rect(obstacleMap, element) for row in obstacleMap for element in row])    

def find_largest_rect(obstacleMap, upper_left_elem):    
    size = 0    
    while not has_obstacles(obstacleMap, upper_left_elem, size+1):    
        size += 1    
    return size    

def has_obstacles(obstacleMap, upper_left_elem, size):    
    #determines if there are obstacles on the on outside square layer    
    #for example, if U is the upper left element and size=3, then has_obstacles checks the elements marked p.    
    # .....    
    # ..U.p    
    # ....p    
    # ..ppp    
    periphery_row = obstacleMap[upper_left_elem.row][upper_left_elem.col:upper_left_elem.col+size]    
    periphery_col = [row[upper_left_elem.col+size] for row in obstacleMap[upper_left_elem.row:upper_left_elem.row+size]    
    return any(is_obstacle(elem) for elem in periphery_row + periphery_col)

def is_obstacle(elem):    
    return elem.value == 'o'    

class MapElement(object):    
    def __init__(self, row, col, value):    
        self.row = row    
        self.col = col    
        self.value = value
+2

: -

isSquare(R,C1,C2) = noObstacle(R,C1,R,C2) && noObstacle(R,C2,R-(C2-C1),C2) && isSquare(R-1,C1,C2-1)

isSquare(R,C1,C2) = square that has bottom side (R,C1) to (R,C2) 

noObstacle(R1,C1,R2,C2) = checks whether there is no obstacle in line segment (R1,C1) to (R2,C2)

Find Max (C2-C1+1) which where isSquare(R,C1,C2) = true

. .

0

More articles:


All Articles