結果
問題 | No.402 最も海から遠い場所 |
ユーザー |
![]() |
提出日時 | 2020-04-18 16:21:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,050 ms / 3,000 ms |
コード長 | 1,705 bytes |
コンパイル時間 | 388 ms |
コンパイル使用メモリ | 82,404 KB |
実行使用メモリ | 298,204 KB |
最終ジャッジ日時 | 2024-10-03 23:53:31 |
合計ジャッジ時間 | 6,477 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
from itertools import permutationsimport syssys.setrecursionlimit(10 ** 6)from bisect import *from collections import *from heapq import *def II(): return int(sys.stdin.readline())def MI(): return map(int, sys.stdin.readline().split())def LI(): return list(map(int, sys.stdin.readline().split()))def SI(): return sys.stdin.readline()[:-1]def LLI(rows_number): return [LI() for _ in range(rows_number)]int1 = lambda x: int(x) - 1def MI1(): return map(int1, sys.stdin.readline().split())def LI1(): return list(map(int1, sys.stdin.readline().split()))p2D = lambda x: print(*x, sep="\n")dij = [(1, 0), (0, 1), (-1, 0), (0, -1)]def main():h,w=MI()ss=[SI() for _ in range(h)]# 陸地に出来る最大正方形を見つける# 参考https://qiita.com/gushwell/items/4ab87b52f6511f11f58d# 左からそのマスまで連続する陸地の数を求めるcc=[[0]*w for _ in range(h)]for i in range(h):for j in range(w):if ss[i][j]=="#":if j:cc[i][j]=cc[i][j-1]+1else:cc[i][j]=1# 上からそのマスまで連続する陸地の数を求めるdd=[[0]*w for _ in range(h)]for j in range(w):for i in range(h):if ss[i][j]=="#":if i:dd[i][j]=dd[i-1][j]+1else:dd[i][j]=1# そのマスを右下とする正方形がとれる、最大の辺の長さqq=[[0]*w for _ in range(h)]for i in range(h):for j in range(w):if cc[i][j]:if i*j:qq[i][j]=min(qq[i-1][j-1]+1,cc[i][j],dd[i][j])else:qq[i][j]=1#p2D(qq)mx=max(max(row) for row in qq)print((mx+1)//2)main()