제출 #1146023

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1146023		mamaniever	Coin Collecting (JOI19_ho_t4)	Java	0 / 100	52 ms	11344 KiB

joi2019_ho_t4

import java.util.*;

class Main {

    // Direcciones para moverse (arriba, abajo, izquierda, derecha)
    private static final int[] DIR_X = {-1, 1, 0, 0};
    private static final int[] DIR_Y = {0, 0, -1, 1};

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt(); // Número de posiciones objetivo
        List<int[]> coins = new ArrayList<>(); // Lista de posiciones de las monedas

        // Leer las posiciones de las monedas
        for (int i = 0; i < 2 * N; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            coins.add(new int[]{x, y});
        }

        // Generar las posiciones objetivo
        List<int[]> targets = new ArrayList<>();
        for (int i = 1; i <= N; i++) {
            targets.add(new int[]{i, 1}); // Fila 1
            targets.add(new int[]{i, 2}); // Fila 2
        }

        // Ordenar las monedas y los objetivos por coordenadas para emparejar eficientemente
        coins.sort(Comparator.comparingInt(a -> a[0]));
        targets.sort(Comparator.comparingInt(a -> a[0]));

        // Calcular la suma de las distancias mínimas usando BFS
        long totalOperations = 0;
        for (int i = 0; i < 2 * N; i++) {
            totalOperations += bfsDistance(coins.get(i), targets.get(i));
        }

        // Imprimir el resultado
        System.out.println(totalOperations);
    }

    /**
     * Calcula la distancia mínima entre dos celdas usando BFS.
     *
     * @param start Posición inicial de la moneda [x, y].
     * @param target Posición objetivo [x, y].
     * @return Distancia mínima entre la posición inicial y la posición objetivo.
     */
    private static int bfsDistance(int[] start, int[] target) {
        Queue<int[]> queue = new LinkedList<>();
        Set<Long> visited = new HashSet<>();

        queue.add(new int[]{start[0], start[1], 0}); // {x, y, distancia}
        visited.add(hash(start[0], start[1]));

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[0], y = current[1], distance = current[2];

            // Si llegamos al objetivo, devolvemos la distancia
            if (x == target[0] && y == target[1]) {
                return distance;
            }

            // Explorar las celdas vecinas
            for (int i = 0; i < 4; i++) {
                int newX = x + DIR_X[i];
                int newY = y + DIR_Y[i];

                long key = hash(newX, newY);
                
                // Limitar el área de búsqueda para evitar exploración infinita
                if (!visited.contains(key) && isValid(newX, newY)) {
                    visited.add(key);
                    queue.add(new int[]{newX, newY, distance + 1});
                }
            }
        }

        return -1; // No debería llegar aquí
    }

    /**
     * Genera un hash único para las coordenadas (x, y).
     */
    private static long hash(int x, int y) {
        return ((long) x << 32) | (y & 0xffffffffL);
    }

    /**
     * Verifica si las coordenadas están dentro de un rango válido.
     */
    private static boolean isValid(int x, int y) {
        // Definir un rango amplio pero limitado para evitar exploración infinita
        return x >= -1000000000 && x <= 1000000000 && y >= -1000000000 && y <= 1000000000;
    }
}

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