Cam thối rữa trong C ++

Giả sử chúng ta có một lưới, ở đây trong mỗi ô có thể có một trong ba giá trị -

• giá trị 0 cho một ô trống;

• giá trị 1 cho một quả cam tươi;

• giá trị 2 cho một quả cam thối.

Trong mỗi phút, bất kỳ quả cam tươi nào tiếp giáp với quả cam thối sẽ trở nên thối rữa.

Chúng ta phải tìm số lần tối thiểu phải trôi qua cho đến khi không có ô nào có màu cam tươi. Nếu không được, hãy trả về -1.

Vì vậy, nếu đầu vào là [[2,1,1], [1,1,0], [0,1,1]], thì đầu ra sẽ là 4

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• phút:=0

• rowMax:=kích thước hàng của lưới

• colMax:=col size của lưới

• FreshLeft:=false

• newGrid:=lưới

• trong khi true là khác 0, do -

  • newGrid:=lưới

  • cờ:=false

  • FreshLeft:=false

  • để khởi tạo i:=0, khi tôi

    • để khởi tạo j:=0, khi j

      • nếu newGrid [i, j] giống với 1, thì -

        • if (i-1> =0 and newGrid [i-1, j] is 2) or (i + 1 =0 and newGrid [ i, j-1] là 2) hoặc (j + 1> =0 và newGrid [i, j + 1] là 2), thì

          • lưới [i, j]:=2

          • cờ:=true

        • FreshLeft:=true

  • nếu cờ khác 0, thì -

    • (tăng 1 phút)

  • Nếu không

    • Ra khỏi vòng lặp

• return (nếu freshLeft không bằng true thì là phút, ngược lại là -1)

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

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

Đầu ra

4