BFS(상하좌우 + 대각선) 유형 너비 우선 탐색
from collections import deque
import sys
input = sys.stdin.readline
N, M = map(int, input().strip().split())
graph = [list(map(int, input().strip().split())) for _ in range(N)]
queue = deque()
def BFS():
while queue:
y, x = queue.popleft()
dy = [0, 1, 1, 1, 0, -1, -1, -1]
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
for i in range(8):
ny = y + dy[i]
nx = x + dx[i]
if nx < 0 or nx >= M or ny < 0 or ny >= N:
continue
if 0 <= ny < N and 0 <= nx < M:
if not graph[ny][nx]:
graph[ny][nx] = graph[y][x] + 1
queue.append([ny, nx])
distance = 0
# 상어의 위치를 기준으로 해당 칸의 안전 거리를 계산
for y in range(N):
for x in range(M):
if graph[y][x] == 1:
queue.append([y, x])
BFS()
# 안전 거리가 가장 큰 칸을 구하기
for i in range(N):
temp = max(graph[i])
distance = max(distance, temp)
print(distance-1)