제출 #1147986

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1147986		machaca_rodrigo	Coin Collecting (JOI19_ho_t4)	Java	0 / 100	74 ms	12628 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 int[][] moves = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };

    public static void bfs(int sr, int sc) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{sr, sc, 0}); 
        visited[sr][sc] = true;

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int r = cell[0], c = cell[1], steps = cell[2];

            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 += steps + 1; 
                        queue.offer(new int[]{nr, nc, steps + 1});
                        visited[nr][nc] = true;
                    }
                }
            }

            for (int[] move : moves) {
                int nr = r + move[0], nc = c + move[1];

                if (nr >= 1 && nr <= 2 && nc >= 1 && nc <= n && !visited[nr][nc]) {
                    queue.offer(new int[]{nr, nc, steps + 1});
                    visited[nr][nc] = true;
                }
            }
        }
    }

    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]++;
        }

        for (int r = 1; r <= 2; r++) {
            for (int c = 1; c <= n; c++) {
                if (cnt[r][c] > 1 && !visited[r][c]) {
                    bfs(r, c);
                }
            }
        }

        System.out.println(ans);
    }
}

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