গলা পেড়া কমলা সমস্যা C++-এ সমাধান

একটি গ্রিডে তিন ধরনের মান থাকে: ০ (খালি সেল), ১ (তাজা কমলা), ২ (গলা পেড়া কমলা)। প্রতিটি মিনিটে, যেকোনো তাজা কমলা যদি একটি গলা পেড়া কমলার পাশে (উপরে, নিচে, বামে, ডানে) থাকে, তবে সেটিও গলা পেড়ে যায়। সব কমলা গলা পেড়াতে যত সময় লাগে তা বের করতে হবে। অসম্ভব হলে -১ রিটার্ন করুন।

উদাহরণ

ইনপুট: [[2,1,1],[1,1,0],[0,1,1]]

আউটপুট: 4

অ্যালগরিদম (BFS পদ্ধতি)

1. সকল গলা পেড়া কমলার (২) পজিশন একটি কিউতে রাখুন।
2. তাজা কমলা (১) এর সংখ্যা গণনা করুন।
3. প্রতি লেভেল (মিনিট) প্রসেস করুন:
   • কিউর সব নোডের জন্য চারদিক চেক করুন।
   • তাজা কমলা পেলে সেটাকে গলা পেড়া করুন, কিউতে যোগ করুন, তাজা কমলার কাউন্ট কমান।
4. যখন কিউ খালি হয়, যদি তাজা কমলা শূন্য হয় তবে মিনিট রিটার্ন করুন, অন্যথায় -১।

C++ কোড উদাহরণ (BFS অপ্টিমাইজড)

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int orangesRotting(vector>& grid) {
        int n = grid.size(), m = grid[0].size();
        queue> q;
        int fresh = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 2) q.push({i, j});
                else if (grid[i][j] == 1) fresh++;
            }
        }
        
        if (fresh == 0) return 0;
        
        int minutes = 0;
        vector> dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        
        while (!q.empty()) {
            int sz = q.size();
            bool converted = false;
            while (sz--) {
                auto [x, y] = q.front(); q.pop();
                for (auto [dx, dy] : dirs) {
                    int nx = x + dx, ny = y + dy;
                    if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == 1) {
                        grid[nx][ny] = 2;
                        q.push({nx, ny});
                        fresh--;
                        converted = true;
                    }
                }
            }
            if (converted) minutes++;
        }
        
        return fresh == 0 ? minutes : -1;
    }
};

int main() {
    Solution ob;
    vector> v = {{2,1,1},{1,1,0},{0,1,1}};
    cout << ob.orangesRotting(v);
    return 0;
}

ইনপুট

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

আউটপুট

4