結果

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

ソースコード

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
            for dx,dy in dir:
                x2 = x + dx
                y2 = y + dy
                if 0 <= x2 < H and 0 <= y2 < W:
                    S0.add(x2 * W + y2)

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

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