C++ এ পচনশীল কমলা

ধরুন আমাদের একটি গ্রিড আছে, এখানে প্রতিটি ঘরে তিনটি মান −

• একটি খালি ঘরের জন্য মান 0;

• একটি তাজা কমলার জন্য মান 1;

• একটি পচা কমলার জন্য মান 2।

প্রতি মিনিটে, একটি পচা কমলার সংলগ্ন যেকোনো তাজা কমলা পচা হয়ে যায়।

কোন সেলের একটি তাজা কমলা না হওয়া পর্যন্ত আমাদের ন্যূনতম কতবার শেষ হতে হবে তা খুঁজে বের করতে হবে। যদি এটি সম্ভব না হয়, তাহলে -1 ফেরত দিন।

সুতরাং, ইনপুট যদি [[2,1,1],[1,1,0],[0,1,1]] এর মত হয়, তাহলে আউটপুট হবে 4

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• মিনিট :=0

• rowMax :=গ্রিডের সারি আকার

• colMax :=গ্রিডের কোল আকার

• freshLeft :=মিথ্যা

• newGrid :=গ্রিড

• সত্য যখন অ-শূন্য, কর −

  • newGrid :=গ্রিড

  • পতাকা :=মিথ্যা

  • freshLeft :=মিথ্যা

  • আরম্ভ করার জন্য i :=0, যখন i

    • j শুরু করার জন্য :=0, যখন j

      • যদি newGrid[i, j] 1 এর মত হয়, তাহলে −

        • যদি (i-1>=0 এবং newGrid[i-1,j] হয় 2) অথবা (i+1 =0 এবং newGrid[ i,j-1] হল 2) অথবা (j+1>=0 এবং newGrid[i,j+1] হল 2), তারপর

          • গ্রিড[i, j] :=2

          • পতাকা :=সত্য

        • freshLeft :=সত্য

  • যদি পতাকা অ-শূন্য হয়, তাহলে −

    • (1 দ্বারা মিনিট বাড়ান)

  • অন্যথায়

    • লুপ থেকে বেরিয়ে আসুন

• প্রত্যাবর্তন (যদি freshLeft সত্যের সমান না হয়, তারপর মিনিট, অন্যথায় -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