bfs

Single Source

class Solution {
    int R, C;
    int[][] dirs = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    int[][] grid;

    int BFS(int row, int col){
        ArrayDeque<int[]> q = new ArrayDeque<>();
        q.addLast(new int[]{row, col});
        // mark as visited

        while(!q.isEmpty()){
            int[] cell = q.removeFirst();
            /* dont process or visit node here! */

            // add all 4 neighbours 
            for(int[] d: dirs){
                int nextRow = cell[0] + d[0], nextCol = cell[1] + d[1];
                
                if(isValid(nextRow, nextCol)){
                    /* process node & mark visited */
                    q.addLast(new int[]{nextRow, nextCol});
                }
            }
        }
    }

    boolean isValid(int row, int col){
        return row >= 0 && row < R &&
            col >= 0 && col < C;
    }
}

Multi-Source BFS:

• Instead of starting bfs with only one source, like Number of Islands (i.e starting w/ one el in Q),
• we add all the rotten oranges at Min 0 to the Q, and start bfs from them

994. Rotting Oranges

class Solution {
    int R, C, fresh;
    int[][] grid;
    int[] d = new int[]{0, 1, 0, -1, 0};
    ArrayDeque<int[]> q = new ArrayDeque<>();
    
    public int orangesRotting(int[][] g) {
        grid = g;
        R = grid.length;
        C = grid[0].length;

        for(int row = 0; row < R; row++)
            for(int col = 0; col < C; col++){
                if(grid[row][col] == 2) 
                    q.addLast(new int[]{row, col, 0});

                if(grid[row][col] == 1) 
                    fresh++;
            }
        
        int ans = bfs();
        
        return fresh == 0 ? ans : -1;
    }

    int bfs(){
        int minute = 0;
        while(!q.isEmpty()){
            int[] cell = q.removeFirst();

            minute = cell[2];
            int nextMinute = cell[2] + 1;

            for(int i = 0; i < 4; i++){
                int nextRow = cell[0] + d[i];
                int nextCol = cell[1] + d[i + 1];
                
                if(isValid(nextRow, nextCol)){
                    grid[nextRow][nextCol] = 2;
                    fresh--;
                    q.addLast(new int[]{nextRow, nextCol, nextMinute});
                }
            }
        }
        return minute;
    }

    boolean isValid(int row, int col){
        return row >= 0 && row < R &&
            col >= 0 && col < C &&
            grid[row][col] == 1;
    }
}