15686号から揚げG 5

N*Nの大きさの町には、家とチキン屋があります.
家(x 1,y 1)とフライドチキン屋(x 2,y 2)との距離(|x 1-x 2|+|y 1-y 2|)をフライドチキン街と呼び、最近のフライドチキン屋を基準に計算します.
都市のフライドチキン街はすべての家のフライドチキン街の和です.
家とフライドチキン店の位置情報を提供し、与えられたフライドチキン店にM個しか残っていないフライドチキン店がすべて休業している場合は、都市のフライドチキン距離が最も小さい場合を考慮しなければならない.
条件:N(2≦N≦50),M(1≦M≦13),1≦家数≦2 N,唐揚げ店数≦13
backtrakingを使ってM個のチキン屋を選びました.
その前に、どの店も事前にすべてのフライドチキン店のためにフライドチキン街を用意していました.
すべてのm個のフライドチキン店を選択した場合、各フライドチキン店と選択したフライドチキン店の距離の中で、最寄りのフライドチキン店を選択し、シティフライドチキン街に追加しました.
このように,すべての場合について都市フライドチキンの距離を求め,その最小値を答えとして出力した.
実施時に少し混同されている以外は、興味深い問題です.

from sys import stdin

def chicken_dist():
    #check를 통해 pick된 치킨집들로 치킨 거리 계산하고 result에 추가
    global check, result, house
    ans = 0
    #각 집에 대해서 선택된 치킨집 중 가장 가까운 거리를 추가
    for home in house:
        #house[home] -> 각 집과 치킨집들과의 거리
        #pick된 치킨집 중에서 제일 가까운거를 선택
        i = 0
        min_dist = float('inf')
        for h in house[home]:
            if check[i] == 1:
                min_dist = min(min_dist, house[home][h])
            i+=1
        ans+=min_dist
    result.append(ans)

def pick_chicken(k, p):
    global check, chicken
    #m개를 다 고르면 치킨거리 계산
    if k == m:
        chicken_dist()
        return
    
    for i in range(p, len(chicken)):
        if check[i] == 0:
            check[i]=1
            pick_chicken(k+1, i+1)
            check[i]=0

#치킨집 최대 13개
#각 집마다 모든 치킨집에 대한 치킨 거리를 구해놓고
#m개의 치킨집을 골랐을 때 치킨 거리를 구한다
#다 해보고 가장 작은애로 한다

n, m = map(int, stdin.readline().split())
city = [list(map(int, stdin.readline().split())) for i in range(n)]

#모든 치킨집과 집의 위치 저장
chicken = []
house = {}
for i in range(n):
    for j in range(n):
        if city[i][j] == 1:
            house[(i,j)] = {}
        elif city[i][j] == 2:
            chicken.append((i,j))

for x in chicken:
    for h in house:
        house[h][x] = abs(x[0]-h[0]) + abs(x[1]-h[1])

#백트래킹을 사용해서 m개를 고르는 경우로 해결
check = [0 for i in range(len(chicken))]
result = []
pick_chicken(0, 0)

print(min(result))