結果

問題 No.402 最も海から遠い場所
ユーザー ntuda
提出日時 2025-02-08 15:16:04
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,240 bytes
コンパイル時間 260 ms
コンパイル使用メモリ 82,312 KB
実行使用メモリ 648,692 KB
最終ジャッジ日時 2025-02-08 15:16:22
合計ジャッジ時間 15,266 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 15 WA * 1 TLE * 2 MLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #

from time import time
st = time()

H,W = map(int,input().split())
S = [input() for _ in range(H)]
INF = 3000
D = [[INF] * W for _ in range(H)]
S0 = set()
S1 = set()
Q = []
dir = []

for i in range(-1,2):
    for j in range(-1,2):
        if i == 0 and j == 0:
            continue
        dir.append((i,j))

def fill(hw):
    x = hw // W
    y = hw % W
    for dx, dy in dir:
        x2 = x + dx
        y2 = y + dy
        if 0 <= x2 < H and 0 <= y2 < W:
            if D[x2][y2] > D[x][y] + 1:
                D[x2][y2] = D[x][y] + 1
                S1.add(x2 * W + y2)

for x in range(H):
    for y in range(W):
        if S[x][y] == ".":
            D[x][y] = 0
            S0.add(x * W + y)

x = 0
for y in range(W):
    if D[x][y] == INF:
        D[x][y] = 1
        S1.add(x * W + y)
x = H - 1
for y in range(W):
    if D[x][y] == INF:
        D[x][y] = 1
        S1.add(x * W + y)
y = 0
for x in range(H):
    if D[x][y] == INF:
        D[x][y] = 1
        S1.add(x * W + y)
y = W - 1
for x in range(H):
    if D[x][y] == INF:
        D[x][y] = 1
        S1.add(x * W + y)

while S0:
    while S0:
        fill(S0.pop())
    S0,S1 = S1,S0

ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans,D[h][w])
print(ans)
0