Q14 Shortest Bridge - LeetCode 934 ( with pair class)

class Solution {
    public int shortestBridge(int[][] grid) {
        /* Q7 of graph playlist , we know there are just 2 islands , therefore we will first
        
        we will traverse the array and fire dfs from the first 1 we encounter to store that 
        island in the queue , then break out of the loop

        now that we have 1 island we will fire BFS , from all 1s of this island which is 
        stored in the queue to find the nearest 1 of 2nd island , the first 1 we encounter
        we will return level of that 1 as that will be no. of 0s to be flipped
        */

        int m = grid.length , n = grid[0].length ;
        LinkedList<pair> q = new LinkedList<>();
        boolean flag = false;
        boolean [][] visited = new boolean[m][n];

        //finding first 1
        for(int i = 0 ;i < m ;i++){
            for(int j = 0 ; j < n ;j++){
                if(grid[i][j] == 1){
                    //firing dfs to find 1st island and store all 1s in Q
                    dfs(grid , i , j , m , n ,visited , q);
                    flag = true;
                    break;
                }
            }
            if(flag) break;
        }

        //firing bfs
        while(q.size()>0){
            pair rem = q.pop();
            int row = rem.x ; int col = rem.y ; int dist = rem.dist;

            for(int i = 0 ;i < 4 ; i++){
                int rowdash = row + dir[i][0];
                int coldash = col + dir[i][1];

                //if valid cell , make it true and add to q
                if(rowdash >=0 && coldash >=0 && rowdash < m && coldash < n && 
                visited[rowdash][coldash] == false ){
                    if(grid[rowdash][coldash] == 1)
                    return dist;    

                    visited[rowdash][coldash] = true;
                    q.addLast(new pair(rowdash ,coldash , dist + 1));
                }
                
            }
            
        }
        return -1;
    }

    public void dfs(int[][] grid , int row , int col , int m , int n ,boolean[][] visited ,
    LinkedList<pair> q){
        if(row < 0 || col < 0 || row >= m || col >= n || visited[row][col] == true || 
        grid[row][col] == 0)
        return;

        //marking the element true and adding it to the q
        visited[row][col] = true;
        q.addLast(new pair(row , col , 0));

        for(int i = 0 ;i < 4 ; i++){
            dfs(grid , row + dir[i][0] ,col + dir[i][1] , m , n ,visited , q);
        }
    }

    //direction array
    public int dir [][] = {{0,1},{1,0},{-1,0},{0,-1}};

    //pair class for row , col and distance
    public class pair{
        int x , y , dist;

        pair(int x , int y , int dist){
            this.x = x; this.y = y ; this.dist = dist;
        }
    }
}