Submission #1147705

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147705		mirko	Coin Collecting (JOI19_ho_t4)	Java	0 / 100	61 ms	11340 KiB

joi2019_ho_t4

package Tareas.Tarea4;

import java.io.*;
import java.util.*;

public class joi2019_ho_t4 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());

        int[] X = new int[2 * N];
        int[] Y = new int[2 * N];

        for (int i = 0; i < 2 * N; i++) {
            st = new StringTokenizer(br.readLine());
            X[i] = Integer.parseInt(st.nextToken());
            Y[i] = Integer.parseInt(st.nextToken());
        }

        System.out.println(solve(N, X, Y));
    }

    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);
        }
    }

    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

    static int bfs(Point start, Point target) {
        Queue<Point> queue = new LinkedList<>();
        Map<Point, Integer> distances = new HashMap<>();

        queue.offer(start);
        distances.put(start, 0);

        while (!queue.isEmpty()) {
            Point current = queue.poll();

            if (current.equals(target)) {
                return distances.get(current);
            }

            for (int i = 0; i < 4; i++) {
                int newX = current.x + dx[i];
                int newY = current.y + dy[i];
                Point next = new Point(newX, newY);

                if (distances.containsKey(next)) {
                    continue;
                }

                queue.offer(next);
                distances.put(next, distances.get(current) + 1);
            }
        }

        return Integer.MAX_VALUE;
    }

    public static int solve(int N, int[] X, int[] Y) {
        int totalMoves = 0;
        List<Point> coins = new ArrayList<>();
        List<Point> targets = new ArrayList<>();

        for (int i = 0; i < 2 * N; i++) {
            coins.add(new Point(X[i], Y[i]));
        }

        for (int x = 1; x <= N; x++) {
            for (int y = 1; y <= 2; y++) {
                targets.add(new Point(x, y));
            }
        }

        int[][] distances = new int[2 * N][2 * N];

        for (int i = 0; i < 2 * N; i++) {
            for (int j = 0; j < 2 * N; j++) {
                distances[i][j] = bfs(coins.get(i), targets.get(j));
            }
        }

        boolean[] usedCoins = new boolean[2 * N];
        boolean[] usedTargets = new boolean[2 * N];

        for (int i = 0; i < 2 * N; i++) {
            int minDist = Integer.MAX_VALUE;
            int bestCoin = -1;
            int bestTarget = -1;

            for (int coin = 0; coin < 2 * N; coin++) {
                if (usedCoins[coin]) continue;
                for (int target = 0; target < 2 * N; target++) {
                    if (usedTargets[target]) continue;
                    if (distances[coin][target] < minDist) {
                        minDist = distances[coin][target];
                        bestCoin = coin;
                        bestTarget = target;
                    }
                }
            }

            totalMoves += minDist;
            usedCoins[bestCoin] = true;
            usedTargets[bestTarget] = true;
        }

        return totalMoves;
    }
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 29
• Subtask 3: 0 / 63