배울점: 바이러스가 활성으로만 되고 퍼뜨리는 상황이 없을때 이걸 타임에 넣어주면 안되기 때문에 이 문제를 해결하는 것이 핵심이었다. 이 문제를 graph를 보면서 바이러스가 가득찬 상황이라면 빠져나오게 하고 그렇지 않으면 계속 나아가도록 하였다. 이 생각을 했냐 못했냐가 핵심이었고 그 다음으로는 한번 틀렸었는데 핵심을 이번에는 0이 없는 상황인데 벽으로 가득차서 없는 상황이면 시간이 1일 수도 있기 때문에 이 상황에서는 0을 출력하도록 하였다. 그리고 시간을 최대한 짧게 되도록 최적화하는 것도 무척 중요했다.

import sys
import copy
from collections import deque
from itertools import combinations

def debug(graph):
  print()
  for i in range(1,n+1):
    for j in range(1,n+1):
      print(graph[i][j], end=' ')
    print()
  print()

def check(graph):
  flag=False
  #O(n^2) = 2500
  for i in range(1,n+1):
    for j in range(1,n+1):
      if graph[i][j] == 0:
        flag=True
        break
  return flag
  
dx=[1,-1,0,0]
dy=[0,0,1,-1]

input=sys.stdin.readline

n, m = map(int,input().split())
graph=[[0]*(1+n) for _ in range(1+n)]
virus=[]
for i in range(1,n+1):
  a=list(map(int,input().split()))
  a=[0]+a
  for j in range(1,n+1):
    #바이러스라면
    if a[j]==2:
      virus.append((i,j))
      graph[i][j] = -2
    #bfs에서 간편성을 위해서 바꿔줌
    elif a[j] == 1:
      graph[i][j] = -1
    else:
      graph[i][j] = a[j]
    
    
      
#activates는 활성 바이러스들의 가능한 조합
activates=list(combinations(virus, m))
INF=int(1e9)
mintime=INF

#10C5=189
for activate in activates:
  #2500 * 189
  copygraph=copy.deepcopy(graph)
  q=deque()
  # worst 5, 189 * 5
  for virus in activate:
    #queue에 virus 위치 장전
    q.append(virus)
    x, y = virus
    copygraph[x][y] = 1
  # 하나의 경우의 수마다의 걸리는 시간
  locmax=0
  while q:
    flag=True
    x, y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if not (1<=nx<=n and 1<=ny<=n ) or copygraph[nx][ny] == -1 or copygraph[nx][ny] >0:
        continue
        #worst 10 * 2500, 10*2500*189
      if copygraph[nx][ny] == -2:
        flag=check(copygraph)
        # 0이 하나라도 없으면
        if not flag:
          locmax=max(locmax,copygraph[x][y])
          break
      copygraph[nx][ny] = copygraph[x][y] + 1
      locmax = max(locmax, copygraph[nx][ny])
      q.append((nx,ny))
    if not flag:
      break
  # 0이 하나라도 있으면 즉 바이러스 퍼뜨리는데 실패한 상황
  if check(copygraph):
    continue
  #debug(copygraph)
  mintime=min(mintime, locmax)

if mintime == INF:
  print(-1)
else:
    #정말로 바이러스가 처음부터 다 퍼져있었는데 벽으로 둘러쌓여있던 경우
  if mintime == 0:
    print(mintime)
  else:
    #시작을 1부터 했으므로
    print(mintime-1)