백준 7569 토마토

백준 7576 토마토의 확장 문제 : http://deque.tistory.com/38

이런 날로 먹을수 있는 문제가 있었다면

7576을 풀때 pair를 안쓰고 2차원 배열을 쓰는건데...

약간 신경쓴 부분은

queue에 int 하나만 넣고 싶어서

K, I, J를 int 하나로 해싱했다.

#define INT_MAX_ 2147480000
#include 
#include 
#include 
#include 

using namespace std;

int M, N, H;

int day;
int max_day = 0;
int box[101][101][101];
int normalTomato[1000001][3];
int normalTomatoSize = 0;
int date[101][101][101];


int main() {
	ifstream inFile("output.txt");
	cin >> M >> N >> H;

	int di[6] = {-1, 0, 1, 0, 0, 0};
	int dj[6] = {0, +1, 0, -1, 0, 0};
	int dk[6] = { 0, 0, 0, 0, -1, 1};

	for (int k = 0; k < H; k++) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				date[k][i][j] = INT_MAX_;
				cin >> box[k][i][j];
				if (box[k][i][j] == 1) {
					normalTomato[normalTomatoSize][0] = k;
					normalTomato[normalTomatoSize][1] = i;
					normalTomato[normalTomatoSize][2] = j;
					normalTomatoSize++;
					date[k][i][j] = 0;
				}
			}
		}
	}
	queue bfs;
	for (int i = 0; i < normalTomatoSize; i++) {
		//day = 0;
		bfs.push(normalTomato[i][0]*1000000 + normalTomato[i][1]*1000 + normalTomato[i][2]);
		bfs.push(-1);
		while ( true ) {
			int now_k = bfs.front() / 1000000;
			int now_i = (bfs.front() - (now_k * 1000000)) / 1000;
			int now_j = bfs.front() % 1000;
			int now_date = date[now_k][now_i][now_j];
			if (bfs.front() == -1) {
				bfs.pop();
				if (bfs.empty()) break;
				bfs.push(-1);
				continue;
			}

			for (int r = 0; r < 6; r++) {
				int next_i = now_i + di[r];
				int next_j = now_j + dj[r];
				int next_k = now_k + dk[r];
				int &next_date = date[next_k][next_i][next_j];
				if (next_i >= 0 && next_i < N && next_j >= 0 && next_j < M && next_k >= 0 && next_k < H) {
					if (box[next_k][next_i][next_j] == 0 || (now_date + 1 < next_date && box[next_k][next_i][next_j] == 1)) {
						bfs.push(next_k * 1000000 + next_i * 1000 + next_j);
						box[next_k][next_i][next_j] = 1;
						next_date = now_date + 1;
					}
				}
			}
			bfs.pop();
		}
	}

	for (int k = 0; k < H; k++) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (box[k][i][j] == 0) {
					cout << -1 << endl;
					return 0;
				}
				if (date[k][i][j] >= max_day && box[k][i][j] == 1) {
					max_day = date[k][i][j];
				}
			}
		}
	}
	cout << max_day << endl;

	return 0;
}

이 문제의 핵심은 이거다

....