# Untitled

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

}
}

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```