제출 #1147984

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1147984		machaca_rodrigo	Coin Collecting (JOI19_ho_t4)	Java	0 / 100	85 ms	13124 KiB

joi2019_ho_t4

import java.util.*;

public class joi2019_ho_t4 {
    static int n;
    static int[][] cnt;
    static long ans = 0;
    static boolean[][] visited;
    static List<int[]> moves = Arrays.asList(
        new int[]{0, 1},   // Derecha
        new int[]{0, -1},  // Izquierda
        new int[]{1, 0},   // Abajo
        new int[]{-1, 0}   // Arriba
    );

    public static void dfs(int r, int c) {
        if (r < 1 || r > 2 || c < 1 || c > n || visited[r][c]) return;
        visited[r][c] = true;

        // Si hay más de 1 elemento en esta celda, buscar dónde moverlo
        if (cnt[r][c] > 1) {
            for (int[] move : moves) {
                int nr = r + move[0], nc = c + move[1];
                if (nr >= 1 && nr <= 2 && nc >= 1 && nc <= n && cnt[nr][nc] == 0) {
                    cnt[nr][nc]++;
                    cnt[r][c]--;
                    ans++;
                    dfs(nr, nc); // Llamada recursiva a la nueva posición
                }
            }
        }

        // Continuar explorando otras posiciones
        for (int[] move : moves) {
            int nr = r + move[0], nc = c + move[1];
            if (nr >= 1 && nr <= 2 && nc >= 1 && nc <= n) {
                dfs(nr, nc);
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int total = 2 * n;
        cnt = new int[3][n + 1];
        visited = new boolean[3][n + 1];
        ans = 0;

        for (int i = 0; i < total; i++) {
            int c = sc.nextInt(), r = sc.nextInt();
            if (r < 1) { ans += (1 - r); r = 1; }
            if (r > 2) { ans += (r - 2); r = 2; }
            if (c < 1) { ans += (1 - c); c = 1; }
            if (c > n) { ans += (c - n); c = n; }
            cnt[r][c]++;
        }

        // Iniciar DFS en cada celda con elementos
        for (int r = 1; r <= 2; r++) {
            for (int c = 1; c <= n; c++) {
                if (cnt[r][c] > 1 && !visited[r][c]) {
                    dfs(r, c);
                }
            }
        }

        System.out.println(ans);
    }
}

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