結果

問題 No.2456 Stamp Art
ユーザー lam6er
提出日時 2025-04-16 15:48:19
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,118 bytes
コンパイル時間 179 ms
コンパイル使用メモリ 81,884 KB
実行使用メモリ 111,848 KB
最終ジャッジ日時 2025-04-16 15:49:19
合計ジャッジ時間 9,863 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    H, W = map(int, sys.stdin.readline().split())
    grid = []
    for _ in range(H):
        line = sys.stdin.readline().strip()
        grid.append(line)
    
    # Precompute prefix sums
    prefix = [[0]*(W+1) for _ in range(H+1)]
    for i in range(1, H+1):
        row_sum = 0
        for j in range(1, W+1):
            row_sum += 1 if grid[i-1][j-1] == '#' else 0
            prefix[i][j] = prefix[i-1][j] + row_sum
    
    min_k = float('inf')
    has_black = False
    for i in range(1, H+1):
        for j in range(1, W+1):
            if grid[i-1][j-1] != '#':
                continue
            has_black = True
            low = 1
            high = min(H, W)
            best = 0
            while low <= high:
                mid = (low + high) // 2
                a_min = max(1, i - mid + 1)
                a_max = min(i, H - mid + 1)
                found = False
                for a in range(a_min, a_max + 1):
                    b_min = max(1, j - (mid - 1))
                    b_max = min(j, W - mid + 1)
                    if b_min > b_max:
                        continue
                    # Check each b in [b_min, b_max]
                    for b in range(b_min, b_max + 1):
                        x1 = a
                        y1 = b
                        x2 = a + mid - 1
                        y2 = b + mid - 1
                        if x2 > H or y2 > W:
                            continue
                        total = prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] + prefix[x1-1][y1-1]
                        if total == mid * mid:
                            found = True
                            break
                    if found:
                        break
                if found:
                    best = mid
                    low = mid + 1
                else:
                    high = mid - 1
            if best == 0:
                best = 1  # since it's black, at least 1x1
            if best < min_k:
                min_k = best
    print(min_k if has_black else 0)

if __name__ == "__main__":
    main()
0