【C++】腐ったオレンジ問題の解法 ― 全てのオレンジが腐るまでの最小時間を求める

問題概要

あるグリッド（2次元配列）が与えられ、各セルには以下の3つの値のいずれかが格納されています。

• 0：空のセル
• 1：新鮮なオレンジ
• 2：腐ったオレンジ

毎分、腐ったオレンジに上下左右で隣接している新鮮なオレンジは腐っていきます。

このとき、グリッド内に新鮮なオレンジが1つもなくなるまでに経過する必要のある最小の時間（分）を求めてください。すべてのオレンジを腐らせることが不可能な場合は -1 を返します。

例えば、入力が [[2,1,1],[1,1,0],[0,1,1]] の場合、出力は 4 となります。

解法のアプローチ

この問題は、腐敗の広がりを毎分シミュレーションすることで解くことができます。手順は以下の通りです。

1. 経過時間を記録する変数 minutes を 0 で初期化します。
2. rowMax にグリッドの行数、colMax に列数を代入します。
3. 新鮮なオレンジが残っているかを示すフラグ freshLeft を false で初期化し、比較用のコピー newGrid を作成します。
4. 無限ループの中で以下の処理を繰り返します。
   • ループの先頭で newGrid を現在のグリッドで更新し、フラグ flag と freshLeft をリセットします。
   • すべてのセルを二重ループで走査し、値が 1（新鮮なオレンジ）のセルについて、上下左右のいずれかに値が 2（腐ったオレンジ）が存在するかを判定します。
   • 隣接する腐ったオレンジが見つかった場合、そのセルを 2 に更新し、flag を true にします。
   • 値が 1 のセルが存在した時点で freshLeft を true にします。
5. 走査後に flag が true（＝この1分で新たな腐敗が発生した）であれば minutes をインクリメントし、false であればループを抜けます。
6. 最後に、freshLeft が false（＝新鮮なオレンジが残っていない）なら minutes を、true なら -1 を返します。

C++での実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int orangesRotting(vector<vector<int>> &grid) {
        int minutes = 0;
        int rowMax = grid.size();
        int colMax = grid[0].size();
        bool freshLeft = false;
        auto newGrid = grid;
        while (true) {
            newGrid = grid;
            bool flag = false;
            freshLeft = false;
            for (int i = 0; i < rowMax; i++) {
                for (int j = 0; j < colMax; j++) {
                    if (newGrid[i][j] == 1) {
                        if ((i - 1 >= 0 && newGrid[i - 1][j] == 2) || (i + 1 < rowMax && newGrid[i + 1][j] == 2) || (j - 1 >= 0 && newGrid[i][j - 1] == 2) || (j + 1 < colMax && newGrid[i][j + 1] == 2)) {
                            grid[i][j] = 2;
                            flag = true;
                        }
                        freshLeft = true;
                    }
                }
            }
            if (flag)
                minutes++;
            else
                break;
        }
        return (freshLeft != true) ? minutes : -1;
    }
};
main() {
    Solution ob;
    vector<vector<int>> v = {{2, 1, 1}, {1, 1, 0}, {0, 1, 1}};
    cout << (ob.orangesRotting(v));
}

入力

{{2, 1, 1}, {1, 1, 0}, {0, 1, 1}}

出力

4

計算量と補足

このシミュレーション手法では、1回の走査に O(行数 × 列数) の計算量がかかり、これを腐敗が広がる回数だけ繰り返すため、最悪の場合 O((行数 × 列数)²) となります。

より効率的にしたい場合は、最初にすべての腐ったオレンジの座標をキューに登録し、幅優先探索（BFS）を用いて一括して腐敗を伝播させる方法が定番です。BFS を使えば全体の計算量を O(行数 × 列数) に抑えられるため、大きなグリッドを扱う際にはこちらのアプローチが推奨されます。