AOJ DPL_3_A Largest Square

備忘録

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_A&lang=jp

回答

import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    H, W = il()
    T = [il() for _ in range(H)]
    dp = [[0] * W for _ in range(H)]

    ret = 0
    for h in range(H):
        for w in range(W):
            if T[h][w] == 1:
                dp[h][w] = 0
            elif h >= 1 and w >= 1:
                dp[h][w] = min(dp[h][w - 1], dp[h - 1][w], dp[h - 1][w - 1]) + 1
            else:
                dp[h][w] = 1
            ret = max(ret, dp[h][w])
    print(ret*ret)


if __name__ == '__main__':
    main()

考え方

タイルの左上から、作ることが出来る最大の正方形を
動的計画法で探索を行なう。

まず、タイルの左上から順に、汚れているか否かを判定する。
汚れている場合には、正方形に含めることが出来ないため、必ず0
汚れていない場合には、探索しているタイルから、
上・左・左上の３マスのうち、最も小さい値に+1したものが作ることができる最大の正方形となる。