C++ में रॉटिंग ऑरेंजेस (सड़ते संतरे)

मान लीजिए हमारे पास एक ग्रिड है, जहां प्रत्येक सेल में तीन मानों में से एक हो सकता है:

0 - खाली सेल
1 - ताजा संतरा
2 - सड़ा हुआ संतरा

हर मिनट, कोई भी ताजा संतरा जो किसी सड़े हुए संतरे के निकट (ऊपर, नीचे, बाएं, दाएं) होता है, वह सड़ जाता है।

हमें न्यूनतम मिनटों की संख्या ज्ञात करनी है जिसके बाद कोई ताजा संतरा न बचे। यदि यह संभव नहीं है, तो -1 वापस करें।

उदाहरण के लिए, इनपुट [[2,1,1],[1,1,0],[0,1,1]] के लिए आउटपुट 4 होगा।

C++ में रॉटिंग ऑरेंजेस (सड़ते संतरे)

समाधान दृष्टिकोण (BFS - बेहतर दृष्टिकोण)

दिए गए कोड में एक सरल सिमुलेशन दृष्टिकोण है, लेकिन BFS (ब्रेडथ-फर्स्ट सर्च) का उपयोग करना अधिक कुशल है। यहां BFS आधारित समाधान है:

सभी सड़े हुए संतरों के निर्देशांक एक कतार में डालें।
ताजा संतरों की गिनती करें।
हर मिनट (लेवल), कतार में मौजूद सभी सड़े संतरों को प्रोसेस करें और उनके निकट के ताजा संतरों को सड़ा हुआ बनाएं।
यदि कोई ताजा संतरा सड़ता है, तो उसे कतार में डालें और गिनती घटाएं।
जब कतार खाली हो जाए, यदि ताजा संतरे बचे हैं तो -1 वापस करें, अन्यथा बीते मिनट वापस करें।

उदाहरण (C++ कोड - BFS दृष्टिकोण)

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

class Solution { 
public: 
    int orangesRotting(vector<vector<int>>& grid) { 
        int n = grid.size(), m = grid[0].size(); 
        queue<pair<int,int>> 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++; 
            } 
        } 
        int minutes = 0; 
        vector<pair<int,int>> dirs = {{1,0},{-1,0},{0,1},{0,-1}}; 
        while (!q.empty() && fresh > 0) { 
            int sz = q.size(); 
            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; 
                        fresh--; 
                        q.push({nx, ny}); 
                    } 
                } 
            } 
            minutes++; 
        } 
        return fresh == 0 ? minutes : -1; 
    } 
}; 

int main() { 
    Solution ob; 
    vector<vector<int>> 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}}