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
import sys
from collections import deque
from itertools import combinations

dirs = (
    (1, 0),
    (-1, 0),
    (0, 1),
    (0, -1),
)

def is_edge(arr, i, j):
    for d_r, d_c in dirs:
        if arr[i+d_r][j+d_c] == 0:
            return True
    return False

def get_edges(arr, i, j):
    arr[i][j] = 2
    res = []
    q = deque([[(i, j)]])
    while len(q) != 0:
        popped = q.popleft()
        for r, c in popped:
            if is_edge(arr, r, c):
                res.append((r, c))
            nxt = []
            for d_r, d_c in dirs:
                if arr[r+d_r][c+d_c] == 1:
                    arr[r+d_r][c+d_c] = 2
                    nxt.append((r+d_r, c+d_c))
            if nxt:
                q.append(nxt)
    return res

N = int(sys.stdin.readline())
arr = [[3] * (N+2)]
for _ in range(N):
    arr.append(list(map(int, f'3 {sys.stdin.readline()} 3'.split())))
arr.append([3] * (N+2))
# print(arr)

edges = []
for i in range(1, len(arr)-1):
    for j in range(1, len(arr[0])-1):
        if arr[i][j] == 1:
            edges.append(get_edges(arr, i, j))
# print(edges)

combi = combinations(edges, 2)
diff_minimum = 10001
diff = ()
for edge_list1, edge_list2 in combi:
    for edge1 in edge_list1:
        for edge2 in edge_list2:
            d = abs(edge1[0]-edge2[0]) + abs(edge1[1]-edge2[1])
            if d < diff_minimum:
                diff_minimum = d
print(diff_minimum - 1)