BJ 15686チキン出前
21155 ワード
https://www.acmicpc.net/problem/15686
M個のフライドチキン店を選んで、それぞれ一番近いフライドチキン店を探して、フライドチキン街を加えればいいです.
M個のフライドチキン店を選んで、それぞれ一番近いフライドチキン店を探して、フライドチキン街を加えればいいです.
package day0223;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class DeliverChicken {
static int N, M, numofChicken = 0, numofHouse = 0, answer = Integer.MAX_VALUE;
static int[] numbers;
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static StringTokenizer st;
static ArrayList<House> houseList;
static ArrayList<Chicken> chickenList;
public static class House{
int x, y;
public House(int x, int y) {
super();
this.x = x;
this.y = y;
}
}
public static class Chicken extends House{
public Chicken(int x, int y) {
super(x, y);
}
}
public static void combination(int cnt, int start) { // M개의 치킨집을 선정해서 계산해보기.
if(cnt == M) {
int sum = 0;
for(House h : houseList) { // 선택된 M개의 치킨집과 집들의 치킨거리 합 계산.
sum += calcDist(h, numbers);
}
if(sum < answer) answer = sum;
return;
}
for(int i = start; i < chickenList.size(); i++) {
numbers[cnt] = i;
combination(cnt + 1, i + 1);
}
}
public static int calcDist(House h, int[] numbers) { // 집과 가장 가까운 치킨집의 거리 계산.
int min_dist = Integer.MAX_VALUE;
int dist;
for(int i = 0; i < M; i++) {
dist = Math.abs(chickenList.get(numbers[i]).x - h.x) + Math.abs(chickenList.get(numbers[i]).y - h.y);
if(dist < min_dist) min_dist = dist;
}
return min_dist;
}
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
houseList = new ArrayList<>();
chickenList = new ArrayList<>();
numbers = new int[M];
for (int i = 0; i < N; i++) { // 입력을 받으며, 집과 치킨집의 좌표를 각각 리스트에 추가.
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < N; j++) {
int tmp = Integer.parseInt(st.nextToken());
if (tmp == 1) {
houseList.add(new House(i, j));
} else if (tmp == 2) {
chickenList.add(new Chicken(i, j));
}
}
}
combination(0, 0);
bw.append(Integer.toString(answer));
bw.flush();
}
}
Reference
この問題について(BJ 15686チキン出前), 我々は、より多くの情報をここで見つけました https://velog.io/@mraz0210/BJ15686-치킨-배달テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol