ゴールド4-2638チーズ

チーズ

https://www.acmicpc.net/problem/2638

方法

この問題は、外の空気を徐々に取り除き、2面以上のチーズに触れ、チーズがすべて消えるまでの時間です.チーズの内側はチーズを取り除くべきではありません.従って、問題条件ではエッジが常に空であるため、0、0位置からBFSまでの両面以上のチーズを順次処理する.

に答える

すべてのチーズが消えるまでドアで繰り返し、1日の変数を増やしました.そしてBFSを0,0を基準として開始し,空きスペースであれば初回アクセスであればアクセス配列に1を加算し,同じ位置にアクセスしない条件を設定した.チーズがあればアクセスの並びが2個未満ならアクセスし、アクセス回数が2になったらtemp backterに入れて除去するチーズを貯蔵します.
BFSが終了するとtempに保存されているチーズはすべてクリアし、board cnt関数で空きスペースの個数を決定し、すべてが空の場合は繰り返し文を終了しday変数を出力する.

コード#コード#

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    private static int[][] board;
    private static int[][] visited;
    private static Queue<Pair> air = new LinkedList<>();
    private static int[][] dir = {{0,1},{1,0},{-1,0},{0,-1}};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");

        final int N = Integer.parseInt(input[0]), M = Integer.parseInt(input[1]);
        board = new int[N][M];
        visited = new int[N][M];

        for(int i=0; i<N; i++) {
            input = br.readLine().split(" ");
            for(int j=0; j<M; j++) {
                board[i][j] = Integer.parseInt(input[j]);
                visited[i][j] = 0;
            }
        }

        int day = 0;

        while(true) {

            day++;
            //System.out.println(day);
            Queue<Pair> temp = new LinkedList<>();

            for(int i=0; i<N; i++) {
                for(int j=0; j<M; j++)
                    visited[i][j] = 0;
            }

            air.add(new Pair(0,0));
            visited[0][0] = 1;

            while (!air.isEmpty()) {

                Pair p = air.poll();

                for (int i = 0; i < 4; i++) {
                    int nx = p.first + dir[i][0];
                    int ny = p.second + dir[i][1];

                    if (nx < 0 || nx >= N || ny < 0 || ny >= M)
                        continue;

                    if (board[nx][ny] == 0 && visited[nx][ny] == 0) {
                        visited[nx][ny]++;
                        air.add(new Pair(nx, ny));
                    }
                    if (board[nx][ny] == 1 && visited[nx][ny] < 2) {
                        if (visited[nx][ny] == 1) {
                            temp.add(new Pair(nx, ny));
                        }
                        visited[nx][ny]++;
                    }
                }
            }

            while(!temp.isEmpty()) {
                Pair p = temp.poll();
                board[p.first][p.second] = 0;
            }

            if(board_cnt(N, M))
                break;
        }

        System.out.println(day);
    }

    private static boolean board_cnt(int N, int M) {

        int cnt = 0;
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(board[i][j] == 0)
                    cnt++;
            }
        }
        return cnt == N * M;
    }

    private static class Pair {
        public int first;
        public int second;

        public Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
    }
}