[백준 7569번] 토마토

 

 

 

 

 

 

풀이

---

7576번 문제랑 똑같은데 Z축이 하나더 추가된 문제이다.

 

기본적인 BFS로 풀면서 한번 갈때마다 카운트를 세주면 풀 수 있는 문제

 

Z축을 [a][b][c] 중 a로할지 c로 할지 잘 정해주고, Que사이즈, 입력받는 배열의 사이즈만 잘 고려해주면 된다.

 

 

 

코드

---

 

#include <iostream>
using namespace std;
 
int que_x[1000001];
int que_y[1000001];
int que_z[1000001];
int head_x, tail_x, head_y, tail_y,head_z,tail_z;
int n, m, h;
long long box[102][102][102];
 
void push(int x, int y, int z) {
    que_x[tail_x++] = x;
    que_y[tail_y++] = y;
    que_z[tail_z++] = z;
    tail_x %= 1000001;
    tail_y %= 1000001;
    tail_z %= 1000001;
}
 
int pop_x() {
    int xx = que_x[head_x];
    head_x++;
    head_x %= 1000001;
    return xx;
}
 
int pop_y() {
    int yy = que_y[head_y];
    head_y++;
    head_y %= 1000001;
    return yy;
}
 
int pop_z() {
    int zz = que_z[head_z];
    head_z++;
    head_z %= 1000001;
    return zz;
 
}
 
void bfs() {
    while (head_x != tail_x) {
        int x = pop_x();
        int y = pop_y();
        int z = pop_z();
 
        if (x + 1 <= n - 1 && box[z][x + 1][y] == 0) {
            push(x + 1, y, z);
            box[z][x + 1][y] = box[z][x][y] + 1;
        }
        if (x - 1 >= 0 && box[z][x - 1][y] == 0) {
            push(x - 1, y, z);
            box[z][x - 1][y] = box[z][x][y] + 1;
        }
        if (y + 1 <= m - 1 && box[z][x][y + 1] == 0) {
            push(x, y + 1, z);
            box[z][x][y + 1] = box[z][x][y] + 1;
        }
        if (y - 1 >= 0 && box[z][x][y - 1] == 0) {
            push(x, y - 1, z);
            box[z][x][y - 1] = box[z][x][y] + 1;
        }
        if (z - 1 >= 0 && box[z-1][x][y] == 0) {
            push(x, y, z-1);
            box[z - 1][x][y] = box[z][x][y] + 1;
        }
        if (z + 1 <= h - 1 && box[z+1][x][y] == 0) {
            push(x, y, z + 1);
            box[z+1][x][y] = box[z][x][y] + 1;
        }
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    int flag = 0, compare_flag = 0;
    head_x = 0;
    tail_x = 0;
    head_y = 0;
    tail_y = 0;
    head_z = 0;
    tail_z = 0;
 
    cin >> m >> n >> h;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < m; k++) {
                cin >> box[i][j][k];
                if (box[i][j][k] == 1) {
                    flag++;
                    push(j, k, i);
                }
            }
        }
    }
 
    bfs();
    int Max = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < m; k++) {
                if (box[i][j][k] != 0 && box[i][j][k] != -1) {
                    compare_flag++;
                }
                if (box[i][j][k] == 0) {
                    cout << -1 << '\n';
                    return 0;
                }
                else if (box[i][j][k] > Max){
                    Max = box[i][j][k];
                }
            }
        }
    }
 
    if (compare_flag == flag) {
        cout << 0 << '\n';
        return 0;
    }
    cout << Max - 1 << '\n';
    return 0;
}