[BOJ 15686]フライドチキン出前(Python)

6538 ワード
ブルトポス コンポジット boj テキストリンク
質問する
フライドチキン
問題の説明
ブルートフォースを利用して都市フライドチキン街の最高価格の問題を求めた.
まず、フライドチキン街の最高価格を探す問題なので、フライドチキン店をM個に固定します.M個のフライドチキン屋を選ぶと必ず最高の価格が出ますから
フライドチキン店と一般店の座標を以下に示します.無作為にM個のフライドチキン屋を選んで、その時のフライドチキン街を探すので、フライドチキン屋と普通の店の座標が必要です.
最後にランダムにM個のフライドチキン屋を選んで当時のフライドチキン街を探しますこれですべての場合の都市フライドチキン街が買えます.
プールコード
from itertools import combinations
import sys

input = sys.stdin.readline
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
chickens = []
houses = []
answer = sys.maxsize
# 그래프에서 치킨집이랑 일반집 찾기.
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            houses.append((i, j))
        elif graph[i][j] == 2:
            chickens.append((i, j))
# 무작위 치킨집을 m개 고르고 도시의 치킨거리를 갱신
for chicken in combinations(chickens, m):
    tot_dist = 0  # 무작위 치킨집 m개 중 도시의 치킨거리
    for house_x, house_y in houses:
        dist = sys.maxsize  # 무작위 치킨집 m개 중 각 집의 치킨거리
        for chicken_x, chicken_y in chicken:
            # 가장 가까운 치킨집 채택
            dist = min(dist, abs((chicken_x - house_x)) + abs((chicken_y - house_y)))
        tot_dist += dist
    answer = min(answer, tot_dist)
print(answer)
[Android]Android開発におけるdip,dpi,density,pxなどの詳細
Vue LifeCycleについて