0
正方行列の場合、各セルは黒（1）か白（0）のいずれかで、境界が黒い最大正方形を見つけることができます。私のコードはPython 2.7で、論理的に正しいのだろうか？パフォーマンスの向上ありがとう。黒い境界線を持つ最大正方形を見つけよう
私の主なアイデアは、上に（連続的に）、左に（連続的に）どれくらい多くの黒いノードがあるかを把握することです。leftとtopのマトリックスが表します。次に、leftとtopのトラッキングに基づいて、どのノードでも、最上部と左側の連続する黒ノードの最小値を見つけようとします。そして、最小値をベースにして正方形が形成できるかどうかを調べます。
A=[[1,1,0,0,0],
[1,1,1,1,1],
[0,0,1,0,1],
[0,0,1,1,1],
[0,0,0,0,0]]
top=[[0] * len(A[0]) for i in range(len(A))]
left=[[0] * len(A[0]) for i in range(len(A))]
result = 0
for i in range(len(A)):
for j in range(len(A[0])):
if A[i][j] == 1:
top[i][j] = top[i-1][j] + 1 if i > 0 else 1
left[i][j] = left[i][j-1] + 1 if j > 0 else 1
print top
print left
for i in range(len(A)):
for j in range(len(A[0])):
if A[i][j] == 1:
top[i][j] = top[i-1][j] + 1 if i > 0 else 1
left[i][j] = left[i][j-1] + 1 if j > 0 else 1
x = min(top[i][j], left[i][j])
if x > 1:
y = min(left[i-x+1][j], top[i][j-x+1])
result = max(result, y)
print result
編集1、j_random_hackerによって指されている問題を、解決します。
A = [[1, 1, 0, 0, 0],
[1, 1, 1, 1, 1],
[0, 0, 1, 0, 1],
[0, 0, 1, 1, 1],
[0, 0, 0, 0, 0]]
A = [[0,1,1],
[1,0,1],
[1,1,1]]
top = [[0] * len(A[0]) for i in range(len(A))]
left = [[0] * len(A[0]) for i in range(len(A))]
result = 0
for i in range(len(A)):
for j in range(len(A[0])):
if A[i][j] == 1:
top[i][j] = top[i - 1][j] + 1 if i > 0 else 1
left[i][j] = left[i][j - 1] + 1 if j > 0 else 1
print top
print left
for i in range(len(A)):
for j in range(len(A[0])):
if A[i][j] == 1:
top[i][j] = top[i - 1][j] + 1 if i > 0 else 1
left[i][j] = left[i][j - 1] + 1 if j > 0 else 1
x = min(top[i][j], left[i][j])
if x > 1:
y = min(left[i - x + 1][j], top[i][j - x + 1])
if x == y:
result = max(result, y)
print result
編集2、j_random_hackerによって問題を解決します。
A = [[0,1,0,0],
[1,1,1,1],
[0,1,0,1],
[0,1,1,1]]
A = [[0,1,1],
[1,0,1],
[1,1,1]]
A = [[1, 1, 0, 0, 0],
[1, 1, 1, 1, 1],
[0, 0, 1, 0, 1],
[0, 0, 1, 1, 1],
[0, 0, 0, 0, 0]]
top = [[0] * len(A[0]) for i in range(len(A))]
left = [[0] * len(A[0]) for i in range(len(A))]
result = 0
for i in range(len(A)):
for j in range(len(A[0])):
if A[i][j] == 1:
top[i][j] = top[i - 1][j] + 1 if i > 0 else 1
left[i][j] = left[i][j - 1] + 1 if j > 0 else 1
print top
print left
for i in range(len(A)):
for j in range(len(A[0])):
if A[i][j] == 1:
top[i][j] = top[i - 1][j] + 1 if i > 0 else 1
left[i][j] = left[i][j - 1] + 1 if j > 0 else 1
x = min(top[i][j], left[i][j])
while x > 1:
y = min(left[i - x + 1][j], top[i][j - x + 1])
if x == y:
result = max(result, y)
break
x -= 1
print result
編集3、新しい修正
A = [[0,1,0,0],
[1,1,1,1],
[0,1,0,1],
[0,1,1,1]]
A = [[1, 1, 0, 0, 0],
[1, 1, 1, 1, 1],
[0, 0, 1, 0, 1],
[0, 0, 1, 1, 1],
[0, 0, 0, 0, 0]]
A = [[0,1,1],
[1,0,1],
[1,1,1]]
top = [[0] * len(A[0]) for i in range(len(A))]
left = [[0] * len(A[0]) for i in range(len(A))]
result = 0
for i in range(len(A)):
for j in range(len(A[0])):
if A[i][j] == 1:
top[i][j] = top[i - 1][j] + 1 if i > 0 else 1
left[i][j] = left[i][j - 1] + 1 if j > 0 else 1
print top
print left
for i in range(len(A)):
for j in range(len(A[0])):
if A[i][j] == 1:
top[i][j] = top[i - 1][j] + 1 if i > 0 else 1
left[i][j] = left[i][j - 1] + 1 if j > 0 else 1
x = min(top[i][j], left[i][j])
while x > 1:
y = min(left[i - x + 1][j], top[i][j - x + 1])
if x <= y:
result = max(result, x)
break
x -= 1
print result
@OhadEytan Nope。ユーザーは、コードが動作することを確信しているようには見えません。また、スタック交換ネットワーク上のどこからでもコードがオフトピックであると思う場合は、そこからオフトピックであるため、コードを閉じます。他の場所で話題になっているかもしれないし、そうでないかもしれないからでもない。コードレビューが移行の対象としてリストされていないのが良い理由です。 – Mast
@Mast私は、OPが[質問]（「http://codereview.stackexchange.com/help/on-topic」）に「はい」と答えていると思う_私の知る限りでは、コードは意図したとおりに動作しますか？ "_ また、"良い理由 "_とそのコメントの[こちら]（http://meta.stackoverflow.com/a/251654/2069380）をご覧ください。 –
@OhadEytan私は[this]（http://meta.stackoverflow.com/a/311349/1014587）とリンクしています。OPがはいと答えるかどうかについては、OPはそれが機能するかどうかを明らかにする必要があります。 'Python 2.7のコードは、論理的に正しいのだろうか？と思っていますが、彼が出力を確認したかどうか疑問に思います。 – Mast