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

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

概要

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

使い方

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

Depends on

• ヒストグラム中の最大長方形 (DP/largest_rectangle_in_histogram.py)

Verified with

• TestCase/AOJ/DPL_3_B.test.py

Code

from DP.largest_rectangle_in_histogram import largest_rectangle_in_histogram


def largest_rectangle_in_grid(grid, wall):
    h = len(grid)
    w = len(grid[0])

    hists = [[0] * w for i in range(h)]
    for j in range(w):
        if grid[0][j] != wall:
            hists[0][j] = 1

    for i in range(1, h):
        for j in range(w):
            if grid[i][j] != wall:
                hists[i][j] = hists[i - 1][j] + 1

    ans = 0
    for hist in hists:
        ans = max(largest_rectangle_in_histogram(hist), ans)
    return ans

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