我有一个问题，我必须找到 n * n 网格中最大的正方形。 例如
. . . . . . # . # . . # . . . . # . # . . # . . .
where the biggest square would be 3 by 3 in the bottom corner. I am supposed to return the most steps someone could take before turning right so that they can repeat this infinitely without hitting a wall "#" or going outside the n * n square which is why the output is one less that the width/length of the square.
My code loops through the grid left to right, top to bottom looking for vertices that face down and to the right. Once it finds one it then looks for the biggest possible vertex facing up and to the right and when it finds that checks all four sides to see whether or not they are made up or .. This code works in under 1 second for me on anything around n = 100, however I need it to run at 1 second for n = 500. Any tips on how I can speed this up?
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)
最佳答案
我可以想到一个O(n^3)算法如下:
- 预先计算4个数组:
top[][]、bottom[][]、left[][]、right[][]，每个数组存储您可以走的方向的最大长度来自(i,j) - 对于每个
(i,j)，将其用作正方形的左下角，对于其每个对角点(i-1, j+1), (i-2, j+2)...等等，测试这些点是否可以用作正方形的右上角。存储过程中最大的正方形边
对于第 1 步，所有 4 个数组都可以在 O(n^2) 中预先计算
对于第 2 步，当我们循环遍历所有 (i,j) 时，对于每个 (i,j) 我们必须看到最多所有对角点最多 n 个，总共我们得到 O(n^3)
第 2 步中的测试可以使用 4 个预先计算的数组在 O(1) 中完成，只需通过检查相应的方向来检查“可能的正方形”的 4 个角是否可以连接起来 (上、下、左、右)
当然，可以做很多小事情来加快速度，例如:
在步骤 2 中，对于每个 (i,j)，仅检查 [current_maximum_diagonal_found ... max(right[i][j],顶部[i][j])]
沿着整个算法更新current_maximum_diagonal_found，以便我们希望得到一些(i,j)，我们不需要检查整个n > 对角点。
但严格来说，它仍然是O(n^3)，但据我所知它应该能够在1秒内运行n~500
关于python - 寻找 n * n 网格中最大的正方形，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35858083/