dsa/Graphs/RottingOranges.java

// https://leetcode.com/problems/rotting-oranges/

import java.util.*;
import java.io.*;

class Main {

    static class Node{
        int row;
        int col;
        int time;

        Node(int row, int col, int time){
            this.row = row;
            this.col = col;
            this.time = time;
        }
    }

    public static int orangesRotting(int grid[][]) {
        int n = grid.length;
        int m = grid[0].length;
        
        Queue<Node> q = new LinkedList<>();
        boolean visited[][] = new boolean[n][m];
        
        // push all rotten orange sources
        for (int i=0; i<n; i++){
            for (int j=0; j<m; j++){
                if (grid[i][j] == 2){
                    q.add(new Node(i,j,0));
                    visited[i][j] = true;
                }
            }
        }
        
        int time = 0; 
        int dr[] = {-1, 0, 1, 0};
        int dc[] = {0, 1, 0, -1};
        
        while (!q.isEmpty()){
            Node node = q.poll();
            time = Math.max(time, node.time);

            for (int k=0; k<4; k++){
                int nr = node.row + dr[k];
                int nc = node.col + dc[k];
                
                if (nr >= 0 && nc >= 0 && nr < n && nc < m &&
                    !visited[nr][nc] && grid[nr][nc] == 1){

                    grid[nr][nc] = 2;
                    visited[nr][nc] = true;
                    q.add(new Node(nr, nc, node.time + 1));
                }
            }
        }
        
        for (int i=0; i<n; i++){
            for (int j=0; j<m; j++){
                if (grid[i][j] == 1) return -1;
            }
        }
        
        return time;
    }


    public static void main(String args[]){

        int grid[][] = {
            {0,1,2},
            {0,1,2},
            {2,1,1}
        };

        int ans = orangesRotting(grid);
        System.out.printf("%d\n", ans);
    }
}