제출 #1146905

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1146905		daniel_lopez	Coin Collecting (JOI19_ho_t4)	Java	0 / 100	82 ms	13132 KiB

joi2019_ho_t4

import java.util.*;

public class joi2019_ho_t4 {
    static class Pair {
        int x, y;
        
        Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
        
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Pair)) return false;
            Pair pair = (Pair) o;
            return x == pair.x && y == pair.y;
        }
        
        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }
    
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static Map<String, Integer> memo;
    static final int INF = Integer.MAX_VALUE;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        
        List<Pair> initialCoins = new ArrayList<>();
        for (int i = 0; i < 2 * N; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            initialCoins.add(new Pair(x, y));
        }
        
        memo = new HashMap<>();
        int result = solveDPIterative(N, initialCoins);
        System.out.println(result == INF ? -1 : result);
        sc.close();
    }
    
    static int solveDPIterative(int N, List<Pair> coins) {
        String initialState = getStateString(coins);
        memo.put(initialState, 0);
        
        boolean changed;
        int maxIterations = 4 * N * N; 
        
        do {
            changed = false;
            Map<String, Integer> currentStates = new HashMap<>(memo);
            
            for (Map.Entry<String, Integer> entry : currentStates.entrySet()) {
                String currentState = entry.getKey();
                int currentMoves = entry.getValue();
                List<Pair> currentCoins = parseStateString(currentState);
                
                for (int coinIndex = 0; coinIndex < currentCoins.size(); coinIndex++) {
                    Pair coin = currentCoins.get(coinIndex);
                    
                    for (int dir = 0; dir < 4; dir++) {
                        int newX = coin.x + dx[dir];
                        int newY = coin.y + dy[dir];
                        
                        if (isValidMove(newX, newY, N, currentCoins, coinIndex)) {
                            List<Pair> newCoins = new ArrayList<>(currentCoins);
                            newCoins.set(coinIndex, new Pair(newX, newY));
                            String newState = getStateString(newCoins);
                            
                            int newMoves = currentMoves + 1;
                            if (!memo.containsKey(newState) || memo.get(newState) > newMoves) {
                                memo.put(newState, newMoves);
                                changed = true;
                            }
                        }
                    }
                }
            }
            
            maxIterations--;
        } while (changed && maxIterations > 0);

        int minMoves = INF;
        for (Map.Entry<String, Integer> entry : memo.entrySet()) {
            List<Pair> stateCoins = parseStateString(entry.getKey());
            if (isGoalState(stateCoins, N)) {
                minMoves = Math.min(minMoves, entry.getValue());
            }
        }
        
        return minMoves;
    }
    
    static List<Pair> parseStateString(String state) {
        List<Pair> coins = new ArrayList<>();
        if (state.isEmpty()) return coins;
        
        String[] pairs = state.split(";");
        for (String pair : pairs) {
            if (!pair.isEmpty()) {
                String[] coords = pair.split(",");
                coins.add(new Pair(Integer.parseInt(coords[0]), Integer.parseInt(coords[1])));
            }
        }
        return coins;
    }
    
    static boolean isValidPosition(int x, int y, int N) {
        return x >= -N && x <= N && y >= -N && y <= N;
    }
    
    static boolean isValidMove(int x, int y, int N, List<Pair> coins, int excludeIndex) {
        if (!isValidPosition(x, y, N)) return false;
        
        for (int i = 0; i < coins.size(); i++) {
            if (i == excludeIndex) continue;
            if (coins.get(i).x == x && coins.get(i).y == y) return false;
        }
        
        return true;
    }
    
    static boolean isGoalState(List<Pair> coins, int N) {
        for (Pair coin : coins) {
            if (coin.x < 1 || coin.x > N || coin.y < 1 || coin.y > 2) {
                return false;
            }
        }
        
        Set<Pair> uniqueCoins = new HashSet<>(coins);
        return uniqueCoins.size() == coins.size();
    }
    
    static String getStateString(List<Pair> coins) {
        List<Pair> sortedCoins = new ArrayList<>(coins);
        sortedCoins.sort((a, b) -> a.x == b.x ? a.y - b.y : a.x - b.x);
        StringBuilder sb = new StringBuilder();
        for (Pair coin : sortedCoins) {
            sb.append(coin.x).append(',').append(coin.y).append(';');
        }
        return sb.toString();
    }
}

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