C++でのオレンジの腐敗

グリッドがあるとします。ここでは、各セルに3つの値のいずれかを含めることができます-

• 空のセルの場合は値0;

• フレッシュオレンジの値1;

• 腐ったオレンジの値は2です。

毎分、腐ったオレンジに隣接する新鮮なオレンジは腐ります。

セルに新鮮なオレンジがなくなるまで経過しなければならない最小回数を見つける必要があります。これが不可能な場合は、-1を返します。

したがって、入力が[[2,1,1]、[1,1,0]、[0,1,1]]の場合、出力は4

これを解決するには、次の手順に従います-

• 分：=0

• rowMax：=グリッドの行サイズ

• colMax：=グリッドの列サイズ

• freshLeft：=false

• newGrid：=grid

• trueがゼロ以外の場合、実行-

  • newGrid：=grid

  • フラグ：=false

  • freshLeft：=false

  • 初期化i：=0の場合、i

    • 初期化j：=0の場合、j

      • newGrid [i、j]が1と同じ場合、-

        • if（i-1> =0 and newGrid [i-1、j] is 2）or（i + 1 =0 and newGrid [ i、j-1]は2）または（j + 1> =0でnewGrid[i、j + 1]は2）の場合、

          • grid [i、j]：=2

          • フラグ：=true

        • freshLeft：=true

  • フラグがゼロ以外の場合、-

    • （分を1増やします）

  • それ以外の場合

    • ループから出てきます

• return（freshLeftが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) or (i + 1 < rowMax && newGrid[i + 1][j] == 2) or (j - 1 >= 0 && newGrid[i][j - 1] == 2) or (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