토마토 (feat. 백준, 7569번)

토마토
https://www.acmicpc.net/problem/7569

7569번: 토마토

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <queue>
#include <tuple>
using namespace std;
int M, N, H, arr[100][100][100], dx[4], dy[4];
void bfs() {
	register int x, y, z;
	queue<tuple<int, int, int>> q;
	for (register int k = 0, i, j; k < H; ++k)
		for (i = 0; i < N; ++i)
			for (j = 0; j < M; ++j)
				if (arr[i][j][k] == 1)
					q.push(make_tuple(i, j, k));
	while (!q.empty()) {
		auto p = q.front(); q.pop();
		x = std::get<0>(p), y = std::get<1>(p), z = std::get<2>(p);
		for (register int d = 0, nx, ny, nz; d < 4; ++d) {
			nx = x + dx[d], ny = y + dy[d];
			if (0 <= nx && nx < N && 0 <= ny && ny < M && arr[nx][ny][z] == 0)
				arr[nx][ny][z] = arr[x][y][z] + 1, q.push(make_tuple(nx, ny, z));
		}
		if (z - 1 >= 0 && arr[x][y][z - 1] == 0)
			arr[x][y][z - 1] = arr[x][y][z] + 1, q.push(make_tuple(x, y, z - 1));
		if (z + 1 < H && arr[x][y][z + 1] == 0)
			arr[x][y][z + 1] = arr[x][y][z] + 1, q.push(make_tuple(x, y, z + 1));
	}
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	dx[0] = 1, dx[1] = -1, dx[2] = dx[3] = 0;
	dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
	cin >> M >> N >> H;
	for (register int k = 0, i, j; k < H; ++k)
		for (i = 0; i < N; ++i)
			for (j = 0; j < M; ++j)
				cin >> arr[i][j][k];
	bfs();
	register int ans = 0;
	for (register int k = 0, i, j; k < H; ++k)
		for (i = 0; i < N; ++i)
			for (j = 0; j < M; ++j)
				if (arr[i][j][k] == 0)
					cout << -1 << "\n", exit(0);
				else
					ans = max(ans, arr[i][j][k]);
	cout << ans - 1;
	return 0;
}
// *&)*@*

이전 '토마토' 문제의 3차원 버전입니다.

이전 문제에서 위 아래에 대한 방향만 추가해서 풀이하면 되므로 이전 문제를 먼저 선행하시길 권장합니다.

토마토 (feat. 백준, 7576번)