Baekjoon-15686-치킨 배달

import sys
input = sys.stdin.readline

N,M = map(int,input().split())
board = []
houses = []
chickens = []
for n in range(N):
    line = list(map(int,input().split()))
    board.append(line)
    for m in range(N):
        if line[m]==1:
            houses.append([n,m])
        if line[m]==2:
            chickens.append([0,n,m])

def check_dist():
    # BFS
    result = 0
    remains = [chickens[i] for i in range(len(chickens)) if remain_chickens[i]==1]
    for x,y in houses:
        dist = int(1e4)
        for _,r,c in remains:
            dist = min(dist, abs(r-x)+abs(c-y))
        result += dist
    return result

answer = int(1e4)
remain_chickens = [1 for _ in range(len(chickens))]
def dfs(nums, idx):
    global answer, remain_chickens
    if nums == 0:
        dist = check_dist()
        if answer > dist:
            answer = dist
    else:
        for i in range(idx,len(chickens)-nums+1):
            remain_chickens[i] = 0
            dfs(nums-1,i+1)
            remain_chickens[i] = 1

dfs(len(chickens)-M ,0)
print(answer)