1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

from collections import deque
import sys
input = sys.stdin.readline

M, N = map(int, input().split())
box = [list(map(int, input().split())) for _ in range(N)]
days = 0

# ============== 1안 (시간초과) =============

def bfs(graph, start, n, m, vistied):
    queue = deque([start])
    dist = 0

    dy = [0,1,0,-1]
    dx = [-1,0,1,0]

    while queue:
        for _ in range(len(queue)):
            y,x = queue.popleft()
            if graph[y][x] == 1:
                return dist
            for i in range(4):
                ny,nx = y+dy[i],x+dx[i]
                if 0<=ny<n and 0<=nx<m and not vistied[ny][nx] and graph[ny][nx]!=-1:
                    queue.append((ny,nx))
                    vistied[ny][nx] = True
        dist += 1
    raise Exception()

try:
    for i in range(N):
        for j in range(M):
            if box[i][j] == 0:
                vistied = [[False] * M for _ in range(N)]
                vistied[i][j] = True
                days = max(days, bfs(box, (i,j), N, M, vistied))
    print(days)
except Exception:
    print(-1)

# =============== 2안 (통과) ===============

queue = deque()
for i in range(N):
    for j in range(M):
        if box[i][j] == 1:
            queue.append((i,j))

def bfs(graph, queue, n, m):
    dy = [0,1,0,-1]
    dx = [-1,0,1,0]

    while queue:
        y,x = queue.popleft()
        for i in range(4):
            ny,nx = y+dy[i],x+dx[i]
            if 0<=ny<n and 0<=nx<m and graph[ny][nx]==0:
                graph[ny][nx] = graph[y][x] + 1
                queue.append((ny,nx))

bfs(box, queue, N, M)
for i in range(N):
    for j in range(M):
        if box[i][j] == 0:
            print(-1)
            exit(0)
        days = max(days, box[i][j])
print(days-1)