BOJ/7569トマト

21603 ワード
BFS テキストリンク
https://noj.am/7569
これは以前bfsの入門時に解いたトマト問題の3次元バージョンです.
2 Dバージョンの問題の内容はよく覚えていませんが、同じ論理を3 Dに拡張すればいいようです.
アクセスはbfsに戻りますが、すべてのシングルポイントをキューに入れてから開始します.
3 D座標をqueueに保存して使用すると
queue<pair<int, pair<int, int>>> q;
q.push({z, {y, x}});

auto [z, yx] = q.top();
auto [y, x] = yx;
pairではなくtupleを使用すると
queue<tuple<int, int, int>> q;
q.push({z, y, x});

auto [z, y, x] =q.top();
コードを簡単に書くことができます.
認識してくれたMalkoring兄さんに感謝します:D
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int m, n, h;
int board[100][100][100];
int ret = INT_MAX;
int dx[] = {1, -1, 0, 0, 0, 0};
int dy[] = {0, 0, 1, -1, 0, 0};
int dz[] = {0, 0, 0, 0, 1, -1};

bool InRange(int z, int y, int x) {
    if (0 <= z && z < h)
        if (0 <= y && y < n)
            if (0 <= x && x < m)
                return true;
    return false;
}

int Bfs() {
    queue<tuple<int, int, int, int>> q;
    for (int i = 0; i < h; ++i)
        for (int j = 0; j < n; ++j)
            for (int k = 0; k < m; ++k)
                if (board[i][j][k] == 1)
                    q.push({i, j, k, 1});

    while (!q.empty()) {
        auto [nz, ny, nx, ns] = q.front();
        q.pop();

        for (int i = 0; i < 6; ++i) {
            int nextZ = nz + dz[i], nextY = ny + dy[i], nextX = nx + dx[i], nextS = ns + 1;
            if (!InRange(nextZ, nextY, nextX)) continue;
            if (board[nextZ][nextY][nextX] == 0) {
                board[nextZ][nextY][nextX] = nextS;
                q.push({nextZ, nextY, nextX, nextS});
            }
        }
    }

    bool flag = true;
    int ret = 0;
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < m; ++k) {
                if (board[i][j][k] == 0) flag = false;
                ret = max(ret, board[i][j][k]);
            }
        }
    }

    if (flag) return ret - 1;
    else return -1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    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 >> board[i][j][k];

    cout << Bfs() << '\n';
}
JAVA-04
レイトレーサーを書く