문제

링크텍스트

난관

• 웹에서 답을 찾아서 풀었다. 반성 !!!
• combinations를 사용해 candidate list를 만드는 법이 좋았다.

결과

i = """5 3
0 0 1 0 0
0 0 2 0 1
0 1 2 0 0
0 0 1 0 0
0 0 0 0 2"""

f = open("in.txt", "w")
f.write(i)
f.close()

import sys
sys.stdin = open('in.txt', 'r')
input = sys.stdin.readline

from itertools import combinations

N, M = map(int, input().split())
d_max = 2*N
c, h = [], []
for y in range(N):
    tmp = list(map(int, input().split()))
#    for x in range(len(tmp)):
    for x in range(N):
        if tmp[x] == 1:
            h.append((y,x))
        elif tmp[x] == 2:
            c.append((y,x))
c0 = list(combinations(c, M))
def f_d_min(c0, h):
    r = 0
    for hy, hx in h:
        tmp_min = d_max
        for y, x in c0:
            if abs(hy-y) + abs(hx-x) < tmp_min:
                tmp_min = abs(hy-y) + abs(hx-x)
        r += tmp_min
    return r
m_r = d_max*N*N*M
for i in c0:
    r = f_d_min(list(i),h)
    if m_r > r:
        m_r = r
print(m_r)