ピザ出前距離(DFS)

インプリメンテーションコード

# 피자 배달 거리 (DFS)
import sys
from itertools import combinations
sys.stdin = open("input.txt", "rt")

def minDis(p, x, y):
    min = 2147000000
    for store in p:
        dis = abs(store[0]-x) + abs(store[1]-y)
        if dis < min:
            min = dis
    return min

if __name__ == "__main__":
    n, m = map(int, input().split())
    board =  []
    for _ in range(n):
        board.append(list(map(int, input().split())))

    pizza = []
    for i in range(n):
        for j in range(n):
            if board[i][j] == 2:
                pizza.append((i,j))

    c = list(combinations(pizza, m))
    res = []
    for p in c:
        tot = 0
        for i in range(n):
            for j in range(n):
                if board[i][j] == 1:
                    tot += minDis(p, i, j)
        res.append(tot)
    
    print(min(res))

模範解答

import sys
sys.stdin=open("input.txt", "r")
def DFS(L, s):
    global res
    if L==m:
        sum=0
        for j in range(len(hs)):
            x1=hs[j][0]
            y1=hs[j][1]
            dis=2147000000
            for x in cb:
                x2=pz[x][0]
                y2=pz[x][1]
                dis=min(dis, abs(x1-x2)+abs(y1-y2))
            sum+=dis
        if sum<res:
            res=sum    
    else:
        for i in range(s, len(pz)):
            cb[L]=i
            DFS(L+1, i+1)
       
if __name__=="__main__":
    n, m=map(int, input().split())
    board=[list(map(int, input().split())) for _ in range(n)]
    hs=[]
    pz=[]
    cb=[0]*m
    res=2147000000
    for i in range(n):
        for j in range(n):
            if board[i][j]==1:
                hs.append((i, j))
            elif board[i][j]==2:
                pz.append((i, j))
    DFS(0, 0)
    print(res)

差異