白駿-トマト[java]

質問元: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を出力します.
入力例1
6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1
サンプル出力1
8
入力例2
6 4
0 -1 0 0 0 0
-1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1
サンプル出力2
-1

問題を解く

import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;


class Main {

    static class Point {
        int x;
        int y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static int[] x = {0, 1, -1, 0};
    static int[] y = {1, 0, 0, -1};
    static Queue<Point> coords;
    static boolean[][] visited;

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

        int [] sizeInput = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int [][] tomatoBox = new int[sizeInput[1]][sizeInput[0]];

        int total = 0;
        coords = new LinkedList<>();
        for(int i = 0; i < tomatoBox.length; i++) {
            int [] line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            for(int j = 0; j < tomatoBox[0].length; j++) {
                tomatoBox[i][j] = line[j];
                if(line[j] == 0)
                    total++;
                else if(line[j] == 1)
                    coords.add(new Point(i, j));
            }
        }
        visited = new boolean[tomatoBox.length][tomatoBox[0].length];
        int before = -1;
        int now = 0;
        int day = 0;
        while(before != now && now < total) {
            before = now;
            now = countDays(tomatoBox, before);
            day++;
        }

        if(before == now)
            System.out.println(-1);
        else
            System.out.println(day);
        br.close();
    }

    public static int countDays(int[][] tomatoBox, int before) {

        int now = before;
        Queue<Point> nextCoords = new LinkedList<>();
        while(!coords.isEmpty()) {
            Point cur = coords.poll();
            visited[cur.x][cur.y] = true;
            for(int i = 0; i < x.length; i++) {
                int nextX = cur.x + x[i];
                int nextY = cur.y + y[i];
                if(nextX >= 0 && nextY >= 0 && nextX < tomatoBox.length && nextY < tomatoBox[0].length) {
                    if(tomatoBox[nextX][nextY] == 0 && !visited[nextX][nextY]) {
                        nextCoords.add(new Point(nextX, nextY));
                        visited[nextX][nextY] = true;
                        tomatoBox[nextX][nextY] = 1;
                        now++;
                    }
                }
            }
        }
        coords = nextCoords;
        return now;
    }
}

BFSアルゴリズムを用いて解いた.
まず、全部で何個の0(熟していないトマト)があるかを確認し、ラウンドごとに新熟トマトの座標でキュー内の座標を更新して確認します.もし、回転終了後に新しく熟成したトマトの増加がなければ、すぐに-1に戻ります.
最終的に、初めて計算したトマトの数がラウンドごとに累計計算したトマトの数と同じで、全部で数ラウンドが過ぎた場合、これが答えです.