반응형
import sys
import itertools
def find_location(city, N):
home = []
chicken = []
for r in range(N):
for c in range(N):
if city[r][c] == 1:
home.append([r,c])
elif city[r][c] == 2:
chicken.append([r,c])
return home, chicken
def cal_distance(home, chicken, n):
home_distance = []
for h in home:
tmp = 2*n
for c in chicken:
tmp_n = abs(h[0]-c[0]) + abs(h[1]-c[1])
if tmp_n < tmp:
tmp = tmp_n
home_distance.append(tmp)
city_distance = sum(home_distance)
return city_distance
def sel_chicken(m, chicken):
possible_chicken = []
for get in range(1,m+1):
possible_chicken = possible_chicken + list(itertools.combinations(chicken,get))
return possible_chicken
if __name__ == '__main__':
N, M = map(int, input().split())
city = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]
home, chicken = find_location(city, N)
possible_chicken = sel_chicken(M, chicken)
possible_dist = []
for c in possible_chicken:
possible_dist.append(cal_distance(home, c, N))
print(min(possible_dist))
반응형