[BOJ]最大の正方形

7541 ワード

パイ DP boj テキストリンク

使用するデータ構造/アルゴリズム

与えられた配列の中で最大の正方形を探す問題.
(0,0)点から(n−1,m−1)点まで巡回し,dpを用いて答えを探す.
各セル(r,c)では、2 x 2の正方形を左+の周囲に上向きに形成するかどうかを決定することができる.
:(r,c),(r-1,c),(r,c-1),(r-1,c-1)
dp[r][c]は左上隅の正方形を格納する.
この時点でmin(dp[r-1][c], dp[r][c-1], dp[r-1][c-1])を得ると、
2 x 2内の左上隅セルの最小正方形の大きさを求めることができます.

dp[r][c] = min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]) + 1

したがって、上記のコードを各セルに適用すると、
正方形の大きさを蓄積することで、最大の正方形の大きさを求めることができます.

コード#コード#

from sys import stdin
input = stdin.readline

n, m = map(int, input().split())
board = []
for _ in range(n):
    board.append([int(x) for x in list(input().strip())])
dp = [[0]*(m+1) for _ in range(n+1)]

for r in range(1, n+1):
    for c in range(1, m+1):
        if board[r-1][c-1] == 1:
            dp[r][c] = min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]) + 1

max_width = max([max(row) for row in dp])
print(max_width**2)

Reference

この問題について([BOJ]最大の正方形), 我々は、より多くの情報をここで見つけました https://velog.io/@jadenkim5179/BOJ-가장-큰-정사각형

テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。

Collection and Share based on the CC Protocol

ステップ書きアルゴリズム(再帰的でないソート)

【AWS/Udacity】AWS クラウドアーキテクト ~First Submit~