| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1146820 | carol | Coin Collecting (JOI19_ho_t4) | Java | 0 ms | 0 KiB |
import java.util.*;
public class Main {
static class Point {
int x, y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Point)) return false;
Point point = (Point) o;
return x == point.x && y == point.y;
}
@Override
public int hashCode() {
return Objects.hash(x, y);
}
}
// Directions for moving: right, left, up, down
static final int[] dx = {1, -1, 0, 0};
static final int[] dy = {0, 0, 1, -1};
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
Point[] coins = new Point[2 * n];
// Read coin positions
for (int i = 0; i < 2 * n; i++) {
int x = scanner.nextInt();
int y = scanner.nextInt();
coins[i] = new Point(x, y);
}
// Create target positions
Point[] targets = new Point[2 * n];
int idx = 0;
for (int x = 1; x <= n; x++) {
for (int y = 1; y <= 2; y++) {
targets[idx++] = new Point(x, y);
}
}
System.out.println(findMinimumMoves(coins, targets));
}
static int findMinimumMoves(Point[] coins, Point[] targets) {
int n = coins.length;
int[][] distances = new int[n][n];
// Calculate distances from each coin to each target
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
distances[i][j] = calculateDistance(coins[i], targets[j]);
}
}
// Use Hungarian algorithm to find minimum total distance
return hungarianAlgorithm(distances);
}
static int calculateDistance(Point start, Point end) {
if (start.equals(end)) return 0;
Queue<Point> queue = new LinkedList<>();
Map<Point, Integer> distance = new HashMap<>();
queue.add(start);
distance.put(start, 0);
while (!queue.isEmpty()) {
Point current = queue.poll();
int dist = distance.get(current);
if (current.equals(end)) {
return dist;
}
// Try all four directions
for (int i = 0; i < 4; i++) {
Point next = new Point(current.x + dx[i], current.y + dy[i]);
if (!distance.containsKey(next)) {
distance.put(next, dist + 1);
queue.add(next);
}
}
}
return -1; // Should never happen given problem constraints
}
// Hungarian Algorithm implementation
static int hungarianAlgorithm(int[][] costMatrix) {
int n = costMatrix.length;
int[] lx = new int[n];
int[] ly = new int[n];
int[] xy = new int[n];
int[] yx = new int[n];
boolean[] S = new boolean[n];
boolean[] T = new boolean[n];
int[] slack = new int[n];
int[] slackx = new int[n];
int[] prev = new int[n];
Arrays.fill(xy, -1);
Arrays.fill(yx, -1);
// Initialize labels
for (int x = 0; x < n; x++) {
lx[x] = costMatrix[x][0];
for (int y = 1; y < n; y++) {
lx[x] = Math.max(lx[x], costMatrix[x][y]);
}
}
int matches = 0;
while (matches < n) {
Arrays.fill(S, false);
Arrays.fill(T, false);
Arrays.fill(prev, -1);
int x = 0;
for (; x < n; x++) {
if (xy[x] == -1) break;
}
for (int y = 0; y < n; y++) {
slack[y] = lx[x] + ly[y] - costMatrix[x][y];
slackx[y] = x;
}
while (true) {
if (augment(x, S, T, lx, ly, xy, yx, slack, slackx, prev, costMatrix)) {
matches++;
break;
}
int delta = Integer.MAX_VALUE;
for (int y = 0; y < n; y++) {
if (!T[y]) delta = Math.min(delta, slack[y]);
}
for (int i = 0; i < n; i++) {
if (S[i]) lx[i] -= delta;
if (T[i]) ly[i] += delta;
}
for (int y = 0; y < n; y++) {
if (!T[y]) slack[y] -= delta;
}
}
}
int totalCost = 0;
for (int x = 0; x < n; x++) {
totalCost += costMatrix[x][xy[x]];
}
return totalCost;
}
static boolean augment(int x, boolean[] S, boolean[] T, int[] lx, int[] ly,
int[] xy, int[] yx, int[] slack, int[] slackx, int[] prev,
int[][] costMatrix) {
int n = costMatrix.length;
S[x] = true;
for (int y = 0; y < n; y++) {
if (T[y]) continue;
int currentSlack = lx[x] + ly[y] - costMatrix[x][y];
if (currentSlack == 0) {
T[y] = true;
if (yx[y] == -1 || augment(yx[y], S, T, lx, ly, xy, yx, slack, slackx, prev, costMatrix)) {
xy[x] = y;
yx[y] = x;
return true;
}
} else if (currentSlack < slack[y]) {
slack[y] = currentSlack;
slackx[y] = x;
}
}
return false;
}
}