1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| n, m = list(map(int, input().split()))
city = []
for _ in range(n):
city.append(list(map(int, input().split())))
houseList = []
chickenList = []
for i in range(n):
for j in range(n):
if city[i][j] == 1:
houseList.append([i,j])
if city[i][j] == 2:
chickenList.append([i,j])
houseChicken = [[0] * len(chickenList) for _ in range(len(houseList))]
for i in range(len(houseList)):
for j in range(len(chickenList)):
houseChicken[i][j] = abs(houseList[i][0] - chickenList[j][0]) + abs(houseList[i][1] - chickenList[j][1])
chickenDistance = 123456789
def bfs(index, choosen):
global chickenDistance
if index > len(chickenList):
return
if len(choosen) == m:
minVal = 0
for i in range(len(houseList)):
localMin = 123456789
for j in choosen:
localMin = min(houseChicken[i][j], localMin)
minVal += localMin
chickenDistance = min(minVal, chickenDistance)
return
bfs(index + 1, choosen)
choosen.append(index)
bfs(index + 1, choosen)
choosen.pop()
bfs(0, [])
print(chickenDistance)
|