-
Notifications
You must be signed in to change notification settings - Fork 0
test
woojong edited this page Jul 14, 2024
·
1 revision
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static List<List<Integer>> stores = new ArrayList<>();
static List<List<Integer>> houses = new ArrayList<>();
static List<List<Integer>> storeIndexCombis = new ArrayList<>();
static List<Integer> list = new ArrayList<>();
static int M;
static int storeCnt = 0;
static int loofCnt = 0;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
int input = Integer.parseInt(st.nextToken());
if (input == 1) {
houses.add(List.of(i, j));
}
if (input == 2) {
stores.add(List.of(i, j));
storeCnt++;
}
}
}
createStoreIndexCombi(M, 0);
int minDsum = Integer.MAX_VALUE;
for (int i = 0; i < storeIndexCombis.size(); i++) {
List<Integer> combi = storeIndexCombis.get(i);
int houseDsum = 0;
for (int j = 0; j < houses.size(); j++) {
List<Integer> house = houses.get(j);
int houseX = house.get(0);
int houseY = house.get(1);
int minCsum = Integer.MAX_VALUE;
for (int k = 0; k < combi.size(); k++) {
List<Integer> store = stores.get(combi.get(k));
int storeX = store.get(0);
int storeY = store.get(1);
int minSum = Math.abs(houseX - storeX) + Math.abs(houseY - storeY);
if (minCsum > minSum) {
minCsum = minSum;
}
}
houseDsum += minCsum;
}
if (minDsum > houseDsum) {
minDsum = houseDsum;
}
}
System.out.println(minDsum);
br.close();
}
private static void createStoreIndexCombi(int choose, int previous) {
if (choose == 0) {
storeIndexCombis.add(List.copyOf(list));
return;
}
if (storeCnt == 1) {
previous = -1;
}
for (int i = previous + 1; i < storeCnt; i++) {
if (loofCnt == 0) {
i = 0;
loofCnt++;
}
list.add(i);
createStoreIndexCombi(choose - 1, i);
list.remove(list.size() - 1);
}
}
}