치킨 배달

p.332

from itertools import combinations


N,M=map(int, input().split())

home=[]
chicken=[]

for i in range(N):
  data=list(map(int, input().split()))
  for j in range(len(data)):
    if data[j]==1: # 집
      home.append((i,j))
    elif data[j]==2: # 치킨집
      chicken.append((i,j))

candidates=list(combinations(chicken, M))

def get_sum(candidates):
  result=0

  for hx, hy in home:
    temp=1e9
    for cx,cy in candidates:
      temp=min(temp,abs(hx-cx)+abs(hy-cy))
    result+=temp
  return result

result=1e9
for candidate in candidates:
  result=min(result, get_sum(candidate))

print(result)