구현, 브루트포스 - 15686번: 치킨 배달

# 현재 있는 치킨집에서 최대 M개까지만 남겨서 도시의 치킨 거리의 최솟값 구하기
from itertools import combinations

n, m = map(int, input().split())
maps = []  # 0: 빈 칸, 1: 집, 2: 치킨집
original_cnt = 0  # 원래 치킨집 개수
chicken_list = []  # 치킨집 좌표 저장 리스트
home_list = []  # 집 좌표 저장 리스트

for i in range(n):
    line = list(map(int, input().split()))
    for j in range(len(line)):
        if line[j] == 1:
            home_list.append([i + 1, j + 1])
        elif line[j] == 2:
            chicken_list.append([i + 1, j + 1])
            original_cnt += 1
    maps.append(line)

# 현재 존재하는 치킨집 개수를 세어서, 최소 몇개 이상 없애야하는지 계산하기(현재 치킨집 갯수 - m)개
min_delete = original_cnt - m

min_city_dist = -1

# 최소 없애야 할 갯수 ~ 전체 치킨집 개수 - 1 의 모든 조합을 생성해서 모든 경우의 수에 도시 치킨거리 계산해서 그 중 최솟값 구하기기
# (최소 폐업 개수 ~ 원래 치킨집 개수 - 1) 하나빼고 다 폐업하는 것 까지 가능
for i in range(min_delete, original_cnt):
    combies = list(combinations(chicken_list, i))

    for delete_list in combies:
        # 현재 경우의 도시의 치킨거리 계산하기
        # 각각의 집에 대해서 가장 가까운 치킨집 거리 계산하기
        city_dist = 0
        for home in home_list:
            home_x, home_y = home[0], home[1]
            home_dist = -1
            for chicken in chicken_list:
                # 현재 치킨집이 폐업 대상이라면 패스
                if chicken in delete_list:
                    continue
                chicken_x, chicken_y = chicken[0], chicken[1]
                dist = abs(home_x - chicken_x) + abs(home_y - chicken_y)
                # 각 집의 거리 갱신
                if home_dist == -1 or dist < home_dist:
                    home_dist = dist
            # 현재 경우의 도시의 치킨거리 구하기(전체 집거리 더한 값)
            city_dist += home_dist
        # 각 경우의 도시의 치킨 거리 중 최소값 갱신
        if min_city_dist == -1 or min_city_dist > city_dist:
            min_city_dist = city_dist

print(min_city_dist)