Q14 Shortest Bridge - LeetCode 934 (without pair class)

class Solution {
    public int shortestBridge(int[][] grid) {
        int m = grid.length , n = grid[0].length ;
        LinkedList<int[]> q = new LinkedList<>();
        boolean flag = false;
        boolean [][] visited = new boolean[m][n];

        for(int i = 0 ;i < m ;i++){
            for(int j = 0 ; j < n ;j++){
                if(grid[i][j] == 1){
                    dfs(grid , i , j , m , n ,visited , q);
                    flag = true;
                    break;
                }
            }
            if(flag) break;
        }

        int distance = 0;
        //firing bfs
        while(q.size()>0){
            int size = q.size();
            while(size-- > 0){
                int[] rem = q.pop();
            
                for(int i = 0 ;i < 4 ; i++){
                    int rowdash = rem[0] + dir[i][0];
                    int coldash = rem[1] + dir[i][1];

                    if(rowdash >= 0 && coldash >=0 && rowdash < m && coldash < n && 
                    visited[rowdash][coldash] == false ){
                        if(grid[rowdash][coldash] == 1)
                        return distance;
                        q.addLast(new int[]{rowdash,coldash});
                        visited[rowdash][coldash] = true;
                    }
                    
                }
            }
            distance ++ ;
        }
        return -1;
    }

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

        visited[row][col] = true;
        q.addLast(new int[]{row,col});

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

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

    // public class pair{
    //     int x , y , dist;

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