白駿7569号です.
https://www.acmicpc.net/problem/7569

質問する

チョルスのトマト農場にはトマトを保管する大きな倉庫がある.トマトは下図のように一個ずつ四角い箱の格子に入れ、箱を垂直に積み上げて倉庫に保管します.

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

入力

1行目は、ブロックサイズを表す2つの整数M、N、およびスタックされたブロック数を表すHを与える.Mは箱の横格子数,Nは箱の縦格子数を表す.しかし,2≦M≦100,2≦N≦100,1≦H≦100であった.2行目から、一番下の箱から一番上の箱まで、中に貯まっているトマトの情報があります.つまり、2行目からN行目まで、箱の中のトマトの情報が与えられます.各行の箱の横線のトマトの状態はM個の整数です.整数1は熟したトマトを表し、整数0は未熟のトマトを表し、整数-1はトマトを含まない格子を表す.このようなN線はH回繰り返し与えられる.
トマトが1つ以上ある場合にのみ入力します.

しゅつりょく

トマトを計算するには少なくとも数日かかります.保存からすべてのトマトが熟成している場合は0を、トマトが熟成していない場合は-1を出力します.

入力例

5 3 1
0 -1 0 0 0
-1 -1 0 1 1
0 0 0 1 1

サンプル出力

-1

考える

前回解決したトマト問題の進化バージョンです.
Javaアルゴリズムの問題を解くには、3 D配列を使用します.

アクション

		// 5, 3, 2
		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken()); // 상자의 가로 칸의 수 x
		N = Integer.parseInt(st.nextToken()); // 상자의 세로 칸의 수 y
		H = Integer.parseInt(st.nextToken()); // 상자의 수 z

		boolean zero = false;
		box = new int[H][N][M];

BFS()メソッドで使用するために配列と変数を最初に作成します.
2.

		boolean zero = false;
		box = new int[H][N][M];

		for(int i=0; i<H; i++) {
			for(int j=0; j<N; j++) {
				String str = br.readLine(); 
				st = new StringTokenizer(str);

				for(int k=0; k<M; k++) {
					int num = Integer.parseInt(st.nextToken());

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

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

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

配列を入力値に一致するように設定し、booleanでzero変数を作成し、0が一度発生した場合はtrueに変換し、falseの場合は直ちに0を出力して終了し、変更可能なトマトがないことを示します.

static void BFS() {
		count = 0;

		while(!que.isEmpty()) {
			Node node = que.poll();

			for(int i=0; i<6; i++) {
				nowX = node.x + dirX[i];
				nowY = node.y + dirY[i];
				nowZ = node.z + dirZ[i];

				if(Range_check() && box[nowZ][nowY][nowX] == 0) {
					box[nowZ][nowY][nowX] = box[node.z][node.y][node.x] + 1;
					que.offer(new Node(nowZ, nowY, nowX));
				}	
			}
		}
	} // End of BFS()

BFS()法は,三次元アレイでない限り,一般的なBFSと特に異なる点はない.
探している場合は、トマトが箱に入っているすべての成熟日を計算するために、以前の値を1から新しい座標値に加算することができます.

box[nowZ][nowY][nowX] = box[node.z][node.y][node.x] + 1;

		int max = Integer.MIN_VALUE / 16;
		for(int num[][] : box) {
			for(int num2[] : num) {						
				for(int num3 : num2) {

					if(num3 == 0) {
						System.out.println(-1);
						return;
					}

					if(max < num3) {
						max = num3;
					}
				}
			}
		}

		System.out.println(max - 1);

最後に、配列全体をナビゲートし、配列の最値を出力することで、トマトの成熟日全体がわかります.
まだ0がある場合は、0を出力してすぐに終了します.
また,開始が1であることを考慮すると,最後の結果値は−1であるべきである.

コード#コード#

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

class Node {
	int z;
	int y;
	int x;

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

public class Main {
	static int box[][][];
	static int dirX[] = {0, 0, -1, 1, 0, 0}; // 상, 하, 좌, 우, 위, 아래
	static int dirY[] = {-1, 1, 0, 0, 0, 0};
	static int dirZ[] = {0, 0, 0, 0, 1, -1};
	static Queue<Node> que = new LinkedList<>();

	static int nowX, nowY, nowZ, N, M, H, count;

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

		// 5, 3, 2
		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken()); // 상자의 가로 칸의 수 x
		N = Integer.parseInt(st.nextToken()); // 상자의 세로 칸의 수 y
		H = Integer.parseInt(st.nextToken()); // 상자의 수 z

		boolean zero = false;
		box = new int[H][N][M];

		for(int i=0; i<H; i++) {
			for(int j=0; j<N; j++) {
				String str = br.readLine(); 
				st = new StringTokenizer(str);

				for(int k=0; k<M; k++) {
					int num = Integer.parseInt(st.nextToken());

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

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

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

		BFS();

		int max = Integer.MIN_VALUE / 16;
		for(int num[][] : box) {
			for(int num2[] : num) {						
				for(int num3 : num2) {

					if(num3 == 0) {
						System.out.println(-1);
						return;
					}

					if(max < num3) {
						max = num3;
					}
				}
			}
		}

		System.out.println(max - 1);

	} // End of main

	static void BFS() {
		count = 0;

		while(!que.isEmpty()) {
			Node node = que.poll();

			for(int i=0; i<6; i++) {
				nowX = node.x + dirX[i];
				nowY = node.y + dirY[i];
				nowZ = node.z + dirZ[i];

				if(Range_check() && box[nowZ][nowY][nowX] == 0) {
					box[nowZ][nowY][nowX] = box[node.z][node.y][node.x] + 1;
					que.offer(new Node(nowZ, nowY, nowX));
				}	
			}
		}
	} // End of BFS()

	static boolean Range_check() {
		return (nowX < M && nowX >= 0 && nowY < N && nowY >= 0 && nowZ < H && nowZ >= 0);
	} // End of Range_check()

} // End of class