リンク

質問リンク

問題の説明

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

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

しゅつりょく

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

I/O例

に答える

bfs、現在はz軸までのbfsの基本例

である

最初に1を入力と、アクセスタグとともに0に再変換され、後でbfsで周囲が徐々に+1し、最高値はday

となる.

でも!訪問中に完熟していないトマト-1があれば

この問題x軸、y軸を変えて考えてみると、長い時間がかかりました...
でもこれほど難しいものはない!

コード#コード#

package Sample;
import java.util.*;
class Toma {
	int x, y, z;
	Toma(int x, int y, int z) {
		this.x = x;
		this.y = y;
		this.z = z;
	}
}
public class Main {	
	static int[][][] tomato;
	static boolean[][][] visited;
	static int[] dx = {0, -1, 0, 0, 1, 0};
	static int[] dy = {0, 0, 1, 0, 0, -1};
	static int[] dz = {1, 0, 0, -1, 0, 0};
	static ArrayList<Toma> ro = new ArrayList<>();
	static int N, H, M;
	static int day = 1;
	public static boolean in_range(int x, int y, int z) {
		return x >= 0 && x < N && y >= 0 && y < M && z >= 0 && z < H;
	}
	public static int bfs() {
		Queue<Toma> q = new LinkedList<>();
		for(int i = 0; i < ro.size(); i++)
		{
			q.add(ro.get(i));
			visited[ro.get(i).x][ro.get(i).y][ro.get(i).z] = true;
		}
		while(!q.isEmpty()) {
			Toma t = q.poll();
			int x = t.x;
			int y = t.y;
			int z = t.z;
			for(int i = 0; i < 6; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				int nz = z + dz[i];
				if(!in_range(nx,ny,nz))
					continue;
				if(!visited[nx][ny][nz] && tomato[nx][ny][nz] == 0)
				{
					tomato[nx][ny][nz] = tomato[x][y][z] + 1;
					q.add(new Toma(nx,ny,nz));
					visited[nx][ny][nz] = true;
				}
			}
		}
		int max = -2;
		for(int i = 0; i < H; i++) {
			for(int x = 0; x < N; x++) {
				for(int y = 0; y < M; y++) {
					if(!visited[x][y][i] && tomato[x][y][i] == 0)
						return -1;
					if(max < tomato[x][y][i])
						max = tomato[x][y][i];
				}
			}
		}
		return max;
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		M = sc.nextInt();
		N = sc.nextInt();
		H = sc.nextInt();
		tomato = new int[N][M][H];
		visited = new boolean[N][M][H];
		for(int h = 0; h < H; h++) {
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < M; j++) {
					tomato[i][j][h] = sc.nextInt();
					if(tomato[i][j][h] == 1) {
						tomato[i][j][h]--;
						ro.add(new Toma(i,j,h));
					}
				}//bfs끝나고 res랑 똑같으면 됨
			}
		}
		System.out.println(bfs());
	}
}