J'ai un problème où je dois trouver le plus grand carré dans une grille n * n. par exemple.

. . . . .
. # . # .
. # . . .
. # . # .
. # . . .

Où le plus grand carré serait 3 par 3 dans le coin inférieur. Je suis censé retourner le plus de pas possible avant de tourner à droite afin de pouvoir répéter cela à l'infini sans heurter un mur "#" ou sortir du carré n * n, c'est pourquoi la sortie est inférieure de un à la largeur / longueur de le carré.

Mon code parcourt la grille de gauche à droite, de haut en bas à la recherche de sommets orientés vers le bas et vers la droite. Une fois qu'il en trouve un, il recherche alors le plus grand sommet possible vers le haut et vers la droite et quand il trouve qu'il vérifie les quatre côtés pour voir s'ils sont constitués ou .. Ce code fonctionne en moins de 1 seconde pour moi sur tout ce qui se situe autour de n = 100, mais j'en ai besoin pour fonctionner à 1 seconde pour n = 500. Des conseils sur la façon d'accélérer cela?

import sys
input = sys.stdin.readline

n = int(input())
maze = [list(input()) for _ in range(n)]

squares = 0
for r in range(n - 1):
    for c in range(n - 1):
        if maze[r][c] == '.' and maze[r][c + 1] == '.' and maze[r + 1]        [c] == '.':
            sides = []
            for i in range(min(n - r - 1, n - c - 1), -1, -1):
                if maze[r + i][c + i] == '.' and maze[r + i][c + i - 1] == '.' and maze[r + i - 1][c + i] == '.':
                    sides = i
                    if maze[r][c : c + sides] == ['.'] * sides and maze[r + sides][c : c + sides] == ['.'] * sides:
                        a = True
                        for j in range(sides):
                            if maze[r + j][c] != '.' or maze[r + j][c + sides] != '.':
                                a = False
                        if a and sides > squares:
                            squares = sides
                            break
            if squares == n - 1:
                break
print(squares)
2
Yunis 8 mars 2016 à 05:56

3 réponses

Meilleure réponse

C'est un problème intéressant. J'ai essayé certaines choses et je me suis retrouvé avec cette implémentation qui est O(n^3). J'ai commenté le code afin que vous puissiez suivre l'idée avec espoir. Il y a encore de la place pour des améliorations de vitesse, mais cette version fait déjà le travail (par exemple avec un labyrinthe de 500x500):

Finished after 0.708 seconds.
Result: 112581 squares found, maximum square (x=13, y=270, size=18).

Voici le code source (Python 3):

import random
import pprint
import time

# small sample maze
maze = ['.....',
        '...#.',
        '.#...',
        '.#.#.',
        '.#...']
# convert to boolean maze
maze_bin = [[True if cell == '.' else False for cell in line] for line in maze]

# uncomment to generate a random maze
# maze_size = 500
# threshold = 0.2
# maze_bin = [[1 if random.random() >= threshold else 0 for _ in range(maze_size)] for _ in range(maze_size)]

# take start time
t1 = time.time()

# rotate the maze (first column becomes first row, first row becomes first column)
maze_bin_rot = [[maze_bin[i][j] for i in range(len(maze_bin))] for j in range(len(maze_bin[0]))]

# horizontal_lengths is a two-dimensional list that contains the number of possible steps to the right for every cell.
horizontal_lengths = []
for line in maze_bin:
    num = 0
    line_lengths = []
    for i in reversed(line):
        line_lengths.append(i*num)
        num = i * (num + i)
    horizontal_lengths.append(tuple(reversed(line_lengths)))

# vertical_lengths is a two-dimensional list that contains the number of possible steps to the bottom for every cell.
vertical_lengths_rot = []
for line in maze_bin_rot:
    num = 0
    line_lengths = []
    for i in reversed(line):
        line_lengths.append(i*num)
        num = i * (num + i)
    vertical_lengths_rot.append(tuple(reversed(line_lengths)))
# do the rotation again to be back in normal coordinates
vertical_lengths = [[vertical_lengths_rot[i][j] for i in range(len(vertical_lengths_rot))] for j in range(len(vertical_lengths_rot[0]))]

# calculate the maximum size of a square that has it's upper left corner at (x, y).
# this is the minimum of the possible steps to the right and to the bottom.
max_possible_square = []
for y in range(len(maze_bin)):
    line = []
    for x in range(len(maze_bin[0])):
        line.append(min(horizontal_lengths[y][x], vertical_lengths[y][x]))
    max_possible_square.append(line)

# search for squares
results = []
max_size_square = (-1, -1, -1)
for y in range(len(max_possible_square)):
    for x in range(len(max_possible_square[0])):
        # start with maximum possible size and decrease size until a square is found.
        for size in reversed(range(1, max_possible_square[y][x]+1)):
            # look at the upper right (x+size,y) and bottom left corner (x,y+size).
            # if it's possible to make at least size steps to the right from the bottom left corner
            # and at least size steps to the bottom from the upper right corner, this is a valid square.
            if horizontal_lengths[y+size][x] >= size and vertical_lengths[y][x+size] >= size:
                results.append((x, y, size+1))
                if size+1 > max_size_square[2]:
                    max_size_square = (x, y, size+1)
                # break after the the largest square with upper left corner (x,y) has been found.
                break

t2 = time.time()

# comment this print section if you use larger grids
print('Maze:')
pprint.pprint(maze_bin)
print('\n')
print('Horizontal possible steps:')
pprint.pprint(horizontal_lengths)
print('\n')
print('Vertical possible steps:')
pprint.pprint(vertical_lengths)
print('\n')
print('Maximum possible size of square:')
pprint.pprint(max_possible_square)
print('\n')
print('Results:')
for square in results:
    print('Square: x={}, y={}, size={}'.format(*square))
print('\n')

# final results
print('Finished after {:.3f} seconds.'.format(t2-t1))
print('Result: {} squares found, maximum square (x={}, y={}, size={}).'.format(len(results), *max_size_square))

J'espère que c'est ce que vous cherchiez. Si vous avez des questions, laissez un commentaire ci-dessous;)

2
Felix 8 mars 2016 à 05:10

Je peux penser à un algorithme O(n^3) comme suit:

  1. Précalculez 4 tableaux: top[][], bottom[][], left[][], right[][], chacun stocke la longueur maximale d'une direction à partir de laquelle (i,j)
  2. Pour chaque (i,j), utilisez-le comme coin inférieur gauche d'un carré, pour chacun de ses points diagonaux (i-1, j+1), (i-2, j+2) ... etc., Testez si ces points peuvent être utilisés comme coin supérieur droit du carré. Stockez le côté carré maximum dans le processus

Pour l'étape 1, les 4 tableaux peuvent être précalculés dans O(n^2)

Pour l'étape 2, alors que nous parcourons tous les (i,j), et pour chaque (i,j), nous devons voir au plus tous les points diagonaux qui sont au maximum n d'entre eux, au total, nous obtenons {{X3 }}

Le test de l'étape 2 peut être fait en O(1) en utilisant les 4 tableaux précalculés, il suffit de vérifier si les 4 coins des "carrés possibles" peuvent être joints en vérifiant les directions correspondantes (haut, bas, gauche, droite)


Bien sûr, il y a beaucoup de petites choses qui peuvent être faites pour accélérer, par exemple:

À l'étape 2, pour chaque (i,j), vérifiez uniquement les points diagonaux qui se trouvent dans la plage [current_maximum_diagonal_found ... max(right[i][j], top[i][j])]

Mettez à jour current_maximum_diagonal_found tout au long de l'algorithme, de sorte que nous espérons pour certains (i,j), nous n'avons pas besoin de vérifier des points diagonaux n entiers.

Mais à proprement parler, c'est toujours O(n^3), mais pour autant que je sache, il devrait pouvoir fonctionner en 1 seconde pendant n~500

3
shole 8 mars 2016 à 04:30

Si nous ne voulons pas énumérer tous les résultats, une optimisation qui peut être utile est la suivante. Il est basé sur la stratégie - "ne continuez pas avec cette cellule si elle ne peut pas conduire à la solution optimale"

for y in range(possible_y_value):
    for x in range(possible_x_value):
        # We are ready to process cell identified by (x,y).
        # Check if max_possible_square_length at this cell is greater than size of best_result seen so far. If so, proceed further, otherwise skip this cell
        if max_possible_square[y][x]+1 > best_result.size:
            # proceed further with the inner most for loop
            ....

Même à l'intérieur de la boucle la plus interne pour, nous pouvons sortir de la boucle à l'itération lorsqu'elle tombe en dessous de la taille du meilleur_résultat vue jusqu'ici

0
zero_to_one 11 mars 2016 à 05:04