토마토

 

예전에 풀었던 그냥 한판짜리 토마토가 기억이났는데, 비슷하지만 조금다르다.

차원이 하나가 더 늘어난 문제,

하지만 풀어보면서 느낀건 로직자체가 변화했거나 하진않았다는것이고,

이를통해서 충분히 BFS로 풀수있었다.

 

#include<cstdio>
#include<iostream>
#include<queue>
#include<utility>
#include<cstring>
#include<cstdlib>
#include<vector>

using namespace std;

struct tdi {
	int x, y, z;
};
int n, m, h;
int map[100][100][100];
int d[100][100][100];
bool dist[100][100][100];//필요한지 안필요한지 모르겠음 지금은

int dx[] = { 0,0,1,-1,0,0 };
int dy[] = { 1,-1,0,0,0,0 };
int dz[] = { 0,0,0,0,1,-1 };
int maxi = 10000000;
int maxim = 0;
vector<tdi> v;
bool no = false;

void bfs() {
	tdi three;

	queue<tdi> q;
	for (int i = 0; i < v.size(); i++) {
		q.push(v[i]);
	}
	maxim = 0;
	while (!q.empty()) {
		int x = q.front().x; int y = q.front().y; int z = q.front().z;
		q.pop();
		for (int i = 0; i < 6; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			int nz = z + dz[i];
			if (nx >= 0 && nx < m && ny >= 0 && ny < n && nz >= 0 && nz < h) {
				if (map[nz][nx][ny] == 0 && d[nz][nx][ny] == 0) {
					map[nz][nx][ny] = 1;
					d[nz][nx][ny] = d[z][x][y] + 1;
					three.x = nx; three.y = ny; three.z = nz;
					maxim = d[nz][nx][ny] > maxim ? d[nz][nx][ny] : maxim;
					q.push(three);
				}
			}
		}
	}
	
}

bool check() {
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < m; j++) {
			for (int k = 0; k < n; k++) {
				if (map[i][j][k] == 0) {
					return false;
				}
			}
		}
	}
	return true;

}

int main() {
	scanf("%d %d %d", &n, &m, &h);
	for (int k = 0; k < h; k++) {
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				scanf("%d", &map[k][i][j]);
				if (map[k][i][j] == 1) {
					tdi t; t.x = i; t.y = j; t.z = k;
					v.push_back(t);
				}
			}
		}
	}
	bfs();
	if (check()) {
		cout << maxim<<endl;
	}
	else
		cout << -1;
	return 0;

}

 

그.. 막뭐 tie해서 묶는게있는거같은데 몰라서 그냥 구조체썼다.

주의 해야할건 안익은 토마토가 익는과정은 분명히 존재하지만, 익을수 없는 부분역시 존재하기때문에 고려해서 마지막에 체크한번 해주는것으로 문제가 끝난다.