この特定のケース（説明したように正方形に限定されます）では、これを行うことができます。
最初に、1 文字だけの「正方形」を考えてみましょう: または のいずれ-か#です。正方形のサイズが、その 1 つの文字が「取得」されているかどうかをテストしているだけであることを確認するのは簡単です。
ここで、4x4 の正方形を考えてみましょう:
--
--
また
[['-','-'],
['-','-']]
最大サイズはどのように計算しますか? 1 つの要素 (たとえば左上) を取得し、それとその 3 つの隣接要素が取得されているかどうかをテストします。
>>> sq= [['-','-'],
... ['-','-']]
>>> sq
[['-', '-'], ['-', '-']]
>>> if(all(sq[i][j]=='-' for i in (0,1) for j in (0,1))): print 4
...
4
したがって、一般的に、正方形を取り、その隣を見てください。ターゲットと同じ形状のマトリックスで実行中のカウントを保持できます。
st='''\
##########
#####----#
##--#----#
##--#----#
##--#----#
##--#----#
#####----#
##########
-####----#
########## '''
def max_size(mat, taken):
"""Find the largest X or a square not taken in the matrix `mat`."""
nrows, ncols = len(mat), len(mat[0])
assert nrows==ncols
dirs=(0,1),(1,0),(1,1) # right, down, right and down
counts = [[0]*ncols for _ in range(nrows)]
for i in reversed(range(nrows)): # for each row
assert len(mat[i]) == ncols # matrix must be rectangular
for j in reversed(range(ncols)): # for each element in the row
if mat[i][j] != taken:
if i < (nrows - 1) and j < (ncols - 1):
add=1+min(counts[i+x][j+y] for x,y in (dirs))
else:
add=1 # edges
counts[i][j]=add
for line in counts: print(line)
return max(c for rows in counts for c in rows) # max X (or Y) number elements
table=[[c for c in s.strip()] for s in st.splitlines()]
print (max_size(table,'#')**2)
この関数は右下隅から始まり、左上隅まで逆方向に機能し、頂点にある可能性のある最大正方形の現在の合計を保持することに注意してください。
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 4, 3, 2, 1, 0]
[0, 0, 2, 1, 0, 4, 3, 2, 1, 0]
[0, 0, 2, 1, 0, 4, 3, 2, 1, 0]
[0, 0, 2, 1, 0, 3, 3, 2, 1, 0]
[0, 0, 1, 1, 0, 2, 2, 2, 1, 0]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 1, 1, 1, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
次に、16 の答えのリターンを 2 乗します (4x4)。各正方形がこの行列のどこに収まるかを計算するのは簡単であることがわかります。すべてが計算され、のタプルをマトリックスまたは別countsのタプルに追加するだけです。(i,j)counts