BOJ 7569トマト


質問する



注意事項


  • できるだけ深いものを選びます.(過去日数)
    アップルが全て熟成している場合は、BFSナビを終了する時です.
    (Q中には熟していないりんごしか入っていません)

  • 質問に最小日数を求めさせます.
    BFSを使用すると、アクセス先がアクセスされなくなり、パスが最小化されます.
    そのため、最小値を得るために除去する必要はない.
    私は考えが浅くて、最小を求めたいです.おかげさまで長い間挿し込みました^^
    私はあなたに最高価格を探してもらいます.あなたが最高価格を探しているからといって反感を持ってはいけません.
    DPだけを解いて、必死に最高値を探しています.(minで解決しようとする)
  • コード#コード#

    // 2021.10.01 14:03:46
    // 7569 https://boj.kr/7569
    #include <bits/stdc++.h>
    using namespace std;
    
    const int dz[6] = {1, -1, 0, 0, 0, 0};
    const int dy[6] = {0, 0, 1, -1, 0, 0};
    const int dx[6] = {0, 0, 0, 0, 1, -1};
    
    int box[101][101][101];
    int n, m, h;
    
    class Node
    {
    public:
        int z, y, x, day;
    
        void ripe()
        {
            box[z][y][x] = 1;
        }
    
        bool isValid()
        {
            return this->z >= 0 && this->z < h && this->y >= 0 && this->y < n && this->x >= 0 && this->x < m;
        }
    };
    
    
    int bfs(vector<Node> &startNodes)
    {
        queue<Node> q;
        for (auto &node : startNodes)
        {
            q.push(node);
        }
    
        int day = 0;
        while (!q.empty())
        {
            Node cur = q.front();
            q.pop();
            day = max(day, cur.day);
    
            for (int next = 0; next < 6; next++)
            {
                Node nextNode = Node({cur.z + dz[next], cur.y + dy[next], cur.x + dx[next], cur.day + 1});
                if (nextNode.isValid() && box[nextNode.z][nextNode.y][nextNode.x] == 0)
                {
                    q.push(nextNode);
                    nextNode.ripe();
                }
            }
        }
    
        return day;
    }
    
    int main()
    {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cin >> m >> n >> h;
    
        vector<Node> startNodes;
        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)
                    {
                        startNodes.push_back(Node({i, j, k, 0}));
                    }
                }
            }
        }
    
        int answer = bfs(startNodes);
    
        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)
                    {
                        cout << -1;
                        return 0;
                    }
        cout << answer;
    }

    結果