Baekjoon-17142-연구소 3

from collections import deque
N,M = map(int,input().split())
board = [list(map(int,input().split())) for _ in range(N)]
viruses = []
for i in range(N):
    for j in range(N):
        if board[i][j] == 2:
            viruses.append([i,j])

virus_idxs = []
answer = int(1e4)
def get_min_times():
    virus = [[0]+viruses[idx] for idx in virus_idxs]
    q = deque(virus)
    visited = [[0]*N for _ in range(N)]
    max_time = 0
    for _,x,y in virus:
        visited[x][y] = 1
    while q:
        d,x,y = q.popleft()
        for dx,dy in [[0,-1],[0,1],[1,0],[-1,0]]:
            nx,ny = x+dx, y+dy
            if 0<=nx<N and 0<=ny<N and visited[nx][ny]==0 and board[nx][ny]!=1:
                visited[nx][ny] = 1
                q.append([d+1,nx,ny])
                if board[nx][ny]==0:
                    max_time = max(max_time, d+1)
    for i in range(N):
        for j in range(N):
            if board[i][j]==0 and visited[i][j]==0:
                return int(1e4)
    return max_time

def set_virus(depth, idx):
    global virus_idxs, answer
    if depth==M:
        answer = min(answer, get_min_times())
    else:
        for i in range(idx, len(viruses)-M+depth+1):
            virus_idxs.append(i)
            set_virus(depth+1,i+1)
            virus_idxs.pop()

set_virus(0,0)
if answer==int(1e4):
    print(-1)
else:
    print(answer)