白駿7576号です.
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がたくさんあります.これが私たちが解決しなければならない問題の核心です.
成熟したトマトを同時に散布してこそ、最小限の日数を見つけることができる.
そのためDFSは非常に困難であり,BFSを用いて問題を解決する必要がある.
BFSを使用するため、キューを作成し、x、y座標値のノードオブジェクトを作成します.
私たちは初めて箱boxの並びを作り、1が現れるとすぐにqueに入れました.
こうしてBFSの閲覧を1の位置で開始する.

アクション

ボックスの範囲に入ります.アクセスはありません.ボックスは0です.if( Range_check() && visit[now_y][now_x] == false && box[now_y][now_x] == 0 )条件を満たす価格はqueに追加されます.
その後visitをtrue値に、アクセスしたボックスを1に変更します.
ここで1に変えた理由は、後で-1に未熟なトマトがあるから
この値を処理するには、BFSナビゲーションが完了した後にゼロ値を検索する必要があります.
BFSが終わってからまだ0が残っていれば、熟したトマトがあるかどうかを意味します.
このように異なる方向の1がqueboxに入る1は徐々に増加する.
さらに探索できる場所がなければ、queはすべて空になり、BFS探索は終了する.
2 D配列を繰り返して、最後のボックスを決定します.
0が存在する場合は、-1を出力して戻ります.
トマトが熟していることを確認したときqueは、1から始まるので、0から計算を開始するために値を出力する.
そして熟したトマトがなかったらcountを生成するとともに、boxという変数を用いて直接フィルタリングすることができる.zero_testをfalseに初期化し、zero_testが最初に作成されると、0が1つある場合、true処理が行われる.boxが既に作成されているがfalseである場合、このボックスには成熟したトマトがないことを示すため、0を直接印刷して戻ります.

TMI

ハンバーガーにトマトが嫌いな人はいますか?
ハンバーガーのトマトはパイナップルピザみたい...

コード#コード#

BFSの使用

import java.util.*;
import java.io.*;

public class Main {
	static int dirX[] = {0, 0, -1, 1};
	static int dirY[] = {-1, 1, 0, 0};
	static int box[][];
	static boolean visit[][];
	static Queue<Node> que = new LinkedList<>();

	static int N, M;
	static int now_x, now_y;
	static int count = 0;

	private static class Node {
		int x;
		int y;

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

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

		boolean zero_test = false;
		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken()); // 가로
		N = Integer.parseInt(st.nextToken()); // 세로

		box = new int[N][M];
		visit = new boolean[N][M];

		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<M; j++) {
				int num = Integer.parseInt(st.nextToken());

				if(num == 1) {
					que.offer(new Node(j, i));
				}
				else if(num == 0) {
					zero_test = true;
				}

				box[i][j] = num;
			}
		}

		if(zero_test == false) {
			System.out.println(0);
			return;
		}

		while( !que.isEmpty() ) {
			BFS(que.size());
			count++;
		}

		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {

				if(box[i][j]== 0) {
					System.out.println(-1);
					return;
				}
			}
		}

		System.out.println(count -1);
	}

	static void BFS(int size) {

		while( size-- >0 ) {
			Node node = que.poll();
			for(int i=0; i<4; i++) {
				now_x = node.x + dirX[i];
				now_y = node.y + dirY[i];

				if( Range_check() && visit[now_y][now_x] == false && box[now_y][now_x] == 0 ) {
					que.offer(new Node(now_x, now_y));
					visit[now_y][now_x] = true;
					box[now_y][now_x] = 1;
				}

			}	
		}
	}

	private static boolean Range_check() {
		return (now_x >= 0 && now_y >= 0 && now_x < M && now_y < N);
	}
}