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