제출 #1146882

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

joi2019_ho_t4

import java.util.*;

class CoinCollectingOptimizedBFS {

    // Direcciones para el BFS: derecha, izquierda, arriba, abajo
    private static final int[] DX = {1, -1, 0, 0};
    private static final 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);
        }
    }

    static class BFSState {
        Position pos;
        long moves;

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

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

        // Lectura y procesamiento de posiciones iniciales
        List<Position> coins = readCoinPositions(sc, totalCoins);
        List<Position> targets = generateTargetPositions(n);

        // Emparejamiento de monedas con objetivos
        long totalMoves = matchCoinsToTargets(coins, targets);

        // Salida del resultado
        System.out.println(totalMoves);
    }

    // Método para leer y ajustar las posiciones de las monedas
    private static List<Position> readCoinPositions(Scanner sc, int totalCoins) {
        List<Position> coins = new ArrayList<>();
        for (int i = 0; i < totalCoins; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            
            // Ajustar posiciones a los límites del tablero
            int n = 0;
            x = Math.max(1, Math.min(x, n));
            y = Math.max(1, Math.min(y, 2));

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

    // Método para generar las posiciones objetivo
    private static List<Position> generateTargetPositions(int n) {
        List<Position> targets = new ArrayList<>();
        for (int x = 1; x <= n; x++) {
            for (int y = 1; y <= 2; y++) {
                targets.add(new Position(x, y));
            }
        }
        return targets;
    }

    // Método para emparejar monedas con objetivos
    private static long matchCoinsToTargets(List<Position> coins, List<Position> targets) {
        long totalMoves = 0;
        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;
            }
        }

        return totalMoves;
    }

    // Método para encontrar el camino más corto usando BFS
    private 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<>();
        boolean[][] visited = new boolean[2001][2001]; // Ajustar según el rango de coordenadas

        queue.offer(new BFSState(start, 0));
        visited[start.x + 1000][start.y + 1000] = true; // Ajustar índices para evitar negativos

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

                // Ajustar índices para evitar negativos
                int adjustedX = newX + 1000;
                int adjustedY = newY + 1000;

                if (!visited[adjustedX][adjustedY]) {
                    queue.offer(new BFSState(new Position(newX, newY), current.moves + 1));
                    visited[adjustedX][adjustedY] = true;
                }
            }
        }

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

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