結果

問題 No.402 最も海から遠い場所
コンテスト
ユーザー lam6er
提出日時 2025-03-26 15:43:59
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,441 bytes
コンパイル時間 217 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 273,364 KB
最終ジャッジ日時 2025-03-26 15:44:19
合計ジャッジ時間 9,678 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 TLE * 1 -- * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    H, W = map(int, sys.stdin.readline().split())
    grid = [sys.stdin.readline().strip() for _ in range(H)]
    
    INF = float('inf')
    distance = [[INF] * W for _ in range(H)]
    q = deque()
    
    # Initialize queue with all sea cells
    for i in range(H):
        for j in range(W):
            if grid[i][j] == '.':
                distance[i][j] = 0
                q.append((i, j))
    
    # Directions for 8-way movement (Chebyshev neighbors)
    dirs = [(-1, -1), (-1, 0), (-1, 1),
            (0, -1),          (0, 1),
            (1, -1),  (1, 0), (1, 1)]
    
    # Multi-source BFS to compute minimum Chebyshev distance from any sea
    while q:
        i, j = q.popleft()
        for di, dj in dirs:
            ni, nj = i + di, j + dj
            if 0 <= ni < H and 0 <= nj < W:
                if distance[ni][nj] == INF:
                    distance[ni][nj] = distance[i][j] + 1
                    q.append((ni, nj))
    
    max_dist = 0
    for i in range(H):
        for j in range(W):
            if grid[i][j] == '#':
                # Calculate the shortest distance to the virtual sea outside the map
                external = min(i + 1, H - i, j + 1, W - j)
                current = min(distance[i][j], external)
                if current > max_dist:
                    max_dist = current
    print(max_dist)

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