Untitled

mail@pastecode.io avatar
unknown
c_cpp
a year ago
2.9 kB
4
Indexable
Never
//{ Driver Code Starts
#include<bits/stdc++.h>
using namespace std;

// } Driver Code Ends
class Solution 
{
     bool isValid (int x, int y, int n, int m) {
        return (0 <= x) && (x < n) && (0 <= y) && (y < m);
    }
    vector<vector<int>> adj(vector<int> current_node, int n, int m) {
        int x = current_node[0], y = current_node[1], t = current_node[2];
        
        vector<vector<int>> adj_list;
        
        vector<int> dx = {1, -1, 0, 0};
        vector<int> dy = {0, 0, 1, -1};
        
        for (int i = 0; i < 4; ++i) {
            int new_x = x + dx[i], new_y = y + dy[i];
            if (isValid(new_x, new_y, n, m))
                adj_list.push_back({new_x, new_y, t+1});
        }
    }
    public:
    //Function to find minimum time required to rot all oranges. 
    int orangesRotting(vector<vector<int>>& grid) {
        // Code here
        int n = grid.size(), m = grid[0].size();
        vector<vector<bool>> visited(n, vector<bool>(m, false));
        vector<vector<int>> dist(n, vector<int>(m, INT_MAX));
        queue<vector<int>> q; // {x, y, time}
        
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == 2) {
                    dist[i][j] = 0;
                    visited[i][j] = true;
                    q.push({i, j, 0});
                } else if (grid[i][j] == 0) {
                    dist[i][j] = 0;
                }
            }
        }
        
        while (!q.empty()) {
            vector<int> current_node = q.front();
            q.pop();
            int current_x = current_node[0], current_y = current_node[1], t = current_node[2];
            
            if (visited[current_x][current_y] || grid[current_x][current_y] == 0)
                continue;
            
            grid[current_x][current_y] = 2;
            dist[current_x][current_y] = t;
            
            // Push adjacent nodes
            for (vector<int> adj_node: adj(current_node, n, m))
                if (!visited[adj_node[0]][adj_node[1]] && grid[adj_node[0]][adj_node[1]] != 0) {
                    visited[adj_node[0]][adj_node[1]] = true;
                    q.push(adj_node);
                }
        }
        
        int max_time = INT_MIN;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                max_time = max(max_time, dist[i][j]);
            }
        }
        
        return max_time;
    }
};

//{ Driver Code Starts.
int main(){
	int tc;
	cin >> tc;
	while(tc--){
		int n, m;
		cin >> n >> m;
		vector<vector<int>>grid(n, vector<int>(m, -1));
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				cin >> grid[i][j];
			}
		}
		Solution obj;
		int ans = obj.orangesRotting(grid);
		cout << ans << "\n";
	}
	return 0;
}
// } Driver Code Ends