グリッド中の最大正方形
(DP/largest_square_in_grid.py)

• View this file on GitHub
• Last update: 2021-05-10 23:34:32+09:00

概要

グリッド中の最大正方形の面積を求めるアルゴリズム。

使い方

largest_square_in_grid(grid: Sequence[Sequence[T]], wall: T) -> int
サイズ $N \times M$ のグリッド grid 中の wall を含まない最大正方形の面積を返す。計算量 $O(NM)$

Verified with

• TestCase/AOJ/DPL_3_A.test.py

Code

def largest_square_in_grid(grid, wall):
    h = len(grid)
    w = len(grid[0])
    dp = [[0] * (w + 1) for i in range(h + 1)]

    ans = 0
    for i in range(h):
        for j in range(w):
            if grid[i][j] == wall:
                dp[i + 1][j + 1] = 0
            else:
                dp[i + 1][j + 1] = min(dp[i][j], dp[i + 1][j], dp[i][j + 1]) + 1
                ans = max(dp[i + 1][j + 1], ans)
    return ans ** 2

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page