제출 #1146888

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

joi2019_ho_t4

import java.util.*;

class Main {
    static int n;
    static long totalMoves = 0;

    // Direcciones para el BFS: derecha, izquierda, arriba, abajo
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    static class Position {
        int x, y;

        Position(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Position)) return false;
            Position p = (Position) o;
            return x == p.x && y == p.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }

        String getKey() {
            return x + "," + y;
        }
    }

    static class BFSState {
        Position pos;
        long moves;

        BFSState(Position pos, long moves) {
            this.pos = pos;
            this.moves = moves;
        }
    }

    // BFS optimizado para encontrar el camino más corto
    static long findShortestPath(Position start, Position target) {
        // Si la distancia Manhattan es menor que un umbral, usamos cálculo directo
        long manhattanDist = Math.abs((long)start.x - target.x) + Math.abs((long)start.y - target.y);
        if (manhattanDist <= 1000) { // Umbral para optimización
            return manhattanDist;
        }

        // Para distancias grandes, usamos BFS con límites optimizados
        Queue<BFSState> queue = new LinkedList<>();
        Map<String, Long> visited = new HashMap<>();

        queue.offer(new BFSState(start, 0));
        visited.put(start.getKey(), 0L);

        // Establecemos límites para la búsqueda basados en la posición objetivo
        int minX = Math.min(start.x, target.x) - 1;
        int maxX = Math.max(start.x, target.x) + 1;
        int minY = Math.min(start.y, target.y) - 1;
        int maxY = Math.max(start.y, target.y) + 1;

        while (!queue.isEmpty()) {
            BFSState current = queue.poll();
            Position pos = current.pos;

            if (pos.equals(target)) {
                return current.moves;
            }

            // Exploramos las cuatro direcciones
            for (int i = 0; i < 4; i++) {
                int newX = pos.x + dx[i];
                int newY = pos.y + dy[i];

                // Verificamos límites optimizados
                if (newX < minX || newX > maxX || newY < minY || newY > maxY) {
                    continue;
                }

                Position newPos = new Position(newX, newY);
                String newKey = newPos.getKey();

                if (!visited.containsKey(newKey)) {
                    queue.offer(new BFSState(newPos, current.moves + 1));
                    visited.put(newKey, current.moves + 1);
                }
            }
        }

        return manhattanDist; // Fallback a distancia Manhattan si BFS falla
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int totalCoins = 2 * n;

        List<Position> coins = new ArrayList<>();
        List<Position> targets = new ArrayList<>();

        // Lectura y procesamiento de posiciones iniciales
        for (int i = 0; i < totalCoins; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();

            // Cálculo de movimientos iniciales a los límites
            if (y < 1) {
                totalMoves += Math.abs(1 - y);
                y = 1;
            }
            if (y > 2) {
                totalMoves += Math.abs(y - 2);
                y = 2;
            }
            if (x < 1) {
                totalMoves += Math.abs(1 - x);
                x = 1;
            }
            if (x > n) {
                totalMoves += Math.abs(x - n);
                x = n;
            }

            coins.add(new Position(x, y));
        }

        // Creación de posiciones objetivo
        for (int x = 1; x <= n; x++) {
            for (int y = 1; y <= 2; y++) {
                targets.add(new Position(x, y));
            }
        }

        // Emparejamiento de monedas con objetivos usando BFS
        boolean[] usedCoins = new boolean[coins.size()];
        boolean[] usedTargets = new boolean[targets.size()];

        // Primera pasada: emparejar monedas en posiciones exactas
        for (int i = 0; i < coins.size(); i++) {
            if (usedCoins[i]) continue;
            Position coin = coins.get(i);

            for (int j = 0; j < targets.size(); j++) {
                if (usedTargets[j]) continue;
                Position target = targets.get(j);

                if (coin.equals(target)) {
                    usedCoins[i] = true;
                    usedTargets[j] = true;
                    break;
                }
            }
        }

        // Segunda pasada: emparejar monedas restantes usando BFS
        for (int i = 0; i < coins.size(); i++) {
            if (usedCoins[i]) continue;
            Position coin = coins.get(i);

            long minDist = Long.MAX_VALUE;
            int bestTarget = -1;

            for (int j = 0; j < targets.size(); j++) {
                if (usedTargets[j]) continue;
                Position target = targets.get(j);

                long dist = findShortestPath(coin, target);
                if (dist < minDist) {
                    minDist = dist;
                    bestTarget = j;
                }
            }

            if (bestTarget != -1) {
                totalMoves += minDist;
                usedCoins[i] = true;
                usedTargets[bestTarget] = true;
            }
        }

        System.out.println(totalMoves);
    }
}

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