Submission #1146829

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146829		carol	Coin Collecting (JOI19_ho_t4)	Java	0 / 100	82 ms	16056 KiB

joi2019_ho_t4

import java.util.*;

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int totalCoins = 2 * N;
        List<Point> coins = new ArrayList<>();
        Set<Point> targets = new HashSet<>();

        // Leer las posiciones de las monedas
        for (int i = 0; i < totalCoins; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            coins.add(new Point(x, y, 0));
        }

        // Definir los puntos objetivo
        for (int x = 1; x <= N; x++) {
            for (int y = 1; y <= 2; y++) {
                targets.add(new Point(x, y, 0));
            }
        }

        int totalMoves = 0;
        boolean[][] visited = new boolean[2000000001][2000000001];

        // Calcular la mínima distancia de cada moneda a un objetivo usando BFS
        for (Point coin : coins) {
            totalMoves += bfs(coin, targets);
        }

        System.out.println(totalMoves);
        sc.close();
    }

    private static int bfs(Point start, Set<Point> targets) {
        Queue<Point> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        queue.offer(new Point(start.x, start.y, 0));
        visited.add(start.x + "," + start.y);

        // Movimientos posibles (arriba, abajo, izquierda, derecha)
        int[][] directions = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };

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

            // Verificar si alcanzamos un destino
            if (targets.contains(new Point(current.x, current.y, 0))) {
                targets.remove(new Point(current.x, current.y, 0)); // Marcar como alcanzado
                return current.moves;
            }

            // Explorar vecinos
            for (int[] dir : directions) {
                int newX = current.x + dir[0];
                int newY = current.y + dir[1];
                String key = newX + "," + newY;

                if (!visited.contains(key)) {
                    visited.add(key);
                    queue.offer(new Point(newX, newY, current.moves + 1));
                }
            }
        }

        return Integer.MAX_VALUE; // No debería ocurrir, ya que siempre hay un camino.
    }
}

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