Submission #1148123

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148123		ruben_ipenza	Coin Collecting (JOI19_ho_t4)	Java	0 / 100	87 ms	13120 KiB

joi2019_ho_t4

import java.util.*;

class joi2019_ho_t4 {
    static class State {
        int x, y, moves;
        State(int x, int y, int moves) {
            this.x = x;
            this.y = y;
            this.moves = moves;
        }
    }

    public static int minMoves(int n, int[][] positions) {
        Set<String> visited = new HashSet<>();
        Queue<State> queue = new LinkedList<>();

        for (int[] pos : positions) {
            queue.offer(new State(pos[0], pos[1], 0));
            visited.add(pos[0] + "," + pos[1]);
        }

        int[][] targets = new int[n * 2][2];
        int index = 0;
        for (int x = 1; x <= n; x++) {
            for (int y = 1; y <= 2; y++) {
                targets[index++] = new int[]{x, y};
            }
        }

        int totalMoves = 0;
        boolean[] assigned = new boolean[n * 2];

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

            int closestTarget = -1, minDist = Integer.MAX_VALUE;
            for (int i = 0; i < targets.length; i++) {
                if (!assigned[i]) {
                    int dist = Math.abs(current.x - targets[i][0]) + Math.abs(current.y - targets[i][1]);
                    if (dist < minDist) {
                        minDist = dist;
                        closestTarget = i;
                    }
                }
            }

            if (closestTarget != -1) {
                totalMoves += minDist;
                assigned[closestTarget] = true;
            }
        }

        return totalMoves;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] positions = new int[2 * n][2];
        for (int i = 0; i < 2 * n; i++) {
            positions[i][0] = scanner.nextInt();
            positions[i][1] = scanner.nextInt();
        }
        scanner.close();

        System.out.println(minMoves(n, positions));
    }
}

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