リンク

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

質問する

チョルスのトマト農場にはトマトを保管する大きな倉庫がある.トマトは下図のように1つずつ四角い格子に入れて倉庫に保管しています.
倉庫に保管されているトマトの中には、熟しているものもあれば、まだ熟していないものもあります.1日保管した後、熟したトマトに隣接する未熟のトマトは、熟したトマトの影響を受けて成熟する.1つのトマトの隣接する場所は、左、右、前、後の4つの方向に位置するトマトを意味する.対角線方向に影響を与えないトマトは、トマトが自分で成熟しないと仮定します.哲洙は倉庫に保管されているトマトが何日で熟れるか、最低日数を知りたいと思っている.
倉庫にトマトのチェックボックスの大きさ、熟したトマトと未熟なトマトの情報を保管している場合、数日後には、トマトが熟しているかどうか、最低日数を求めるプログラムを作成します.しかし、箱のいくつかの格にはトマトが入っていないかもしれません.

入力

最初の行は、ボックスのサイズを表す2つの整数M,Nを与える.Mは箱の横格子数,Nは箱の縦格子数を表す.しかし,2≦M,N≦1000であった.2行目から、1つの箱に保存されているトマトの情報が提供されます.つまり、2行目からN行目まで、箱の中のトマトの情報が出てきます.1本の線上で、箱の横線のトマトの状態はM個の整数である.整数1は熟したトマトを表し、整数0は未熟のトマトを表し、整数-1はトマトを含まない格子を表す.
トマトが1つ以上ある場合にのみ入力します.

しゅつりょく

トマトがすべて熟成した最小日付を印刷します.保存からすべてのトマトが熟成している場合は0を、トマトが熟成していない場合は-1を出力します.

に答える

import java.util.*;

class tomato {
    int x; // 세로
    int y; // 가로

    tomato(int x, int y) {
        this.x = x; // 세로
        this.y = y; // 가로
    }
}

public class boj_7576 {
    static int M; // 가로
    static int N; // 세로
    static int[] dx = {-1, 1, 0, 0}; // 상하좌우위아래
    static int[] dy = {0, 0, -1, 1}; // 상하좌우위아래
    static int[][] board; // 토마토 판
    static Queue<tomato> que;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        M = sc.nextInt(); // 가로
        N = sc.nextInt(); // 세로
        board = new int[N][M]; // 토마토판
        que = new LinkedList<>(); // 토마토판 입력
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                board[i][j] = sc.nextInt();
                // 만약 토마토가 익은거라면 큐에 넣어
                if (board[i][j] == 1)
                    que.add(new tomato(i, j));
            }
        }
        System.out.println(BFS());
    }

    public static int BFS() {
        while (!que.isEmpty()) {
            tomato t = que.remove();
            int x = t.x; // 세로
            int y = t.y; // 가로
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i]; // 세로
                int ny = y + dy[i]; // 가로
                // 범위 안에서
                if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
                    // 토마토가 안익었으면
                    if (board[nx][ny] == 0) {
                        // 익은 토마토 추가
                        que.add(new tomato(nx, ny));
                        // 익은 날자를 얻기위해 그 전 값에서 1 증가
                        board[nx][ny] = board[x][y] + 1;
                    }
                }
            }
        }
        // 최대 날짜
        int result = Integer.MIN_VALUE;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                // 토마토가 안익은게 있으면
                if (board[i][j] == 0)
                    return -1; // 날짜 최댓값 구하기
                result = Math.max(result, board[i][j]);
            }
        }
        // 토마토가 모두 익은 상태인 경우
        if (result == 1)
            return 0;
            // 걸린 일수는 최대 날짜에서 1을 빼줘야 함
        else return result - 1;
    }
}

説明:

まだ見慣れないグラフを探しています...参考ブログを見て、続けて、理解しようと努力します.

リファレンス

https://yongku.tistory.com/entry/%EB%B0%B1%EC%A4%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-7576%EB%B2%88-%ED%86%A0%EB%A7%88%ED%86%A0-%EC%9E%90%EB%B0%94Java