934. Shortest Bridge

Link

Solution

這題想法上就是先找出一個island，然後再透過BFS的方式看到達另一個island要多少degree。

但會遭遇許多技術困難，不知道怎麼implement:

1. 如何找到第一個island : 透過DFS把第一個找到的island node value都變成2，然後另一個island node加入BFS的queue中

2. 如何標記已經visited過的node: 透過boolean array紀錄

  public int shortestBridge(int[][] A) {
        int m = A.length;
        int n = A[0].length;
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        boolean found = false;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(A[i][j] == 1 && !found){
                    dfs(A, i, j);
                    found = true;
                }
                else if(A[i][j] == 1 && found){
                    if(( i - 1 >= 0 && A[i-1][j] == 0) 
                        ||( i + 1 < m && A[i+1][j] == 0) 
                        || ( j + 1 < n && A[i][j+1] == 0) 
                        || ( j - 1 >= 0 && A[i][j-1] == 0)){
                        queue.add(new int[]{i,j});
                        visited[i][j] = true;
                    }
                }
            }
        }
        
        //BFS
        int count = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int k = 0; k < size; k++){
                int[] point = queue.poll();
                int i = point[0];
                int j = point[1];
                if(A[i][j] == 2){
                    return count-1; //初始不算
                }
                
                if(i > 0 && !visited[i-1][j]){
                    visited[i-1][j] = true;
                    queue.add(new int[]{i-1, j});
                }
                
                if(j > 0 && !visited[i][j-1]){
                    visited[i][j-1] = true;
                    queue.add(new int[]{i, j-1});
                }
                
                if(i < m-1 && !visited[i+1][j]){
                    queue.add(new int[]{i+1, j});
                    visited[i+1][j] = true;
                }
                
                if(j < n-1 && !visited[i][j+1]){
                    queue.add(new int[]{i, j+1});
                    visited[i][j+1] = true;
                }
            }
            count++;
        }
        return -1;   
                       
    }
    public void dfs(int[][] A, int i , int j){
        if(i < 0 || j < 0 || i >= A.length 
           || j >= A[0].length || A[i][j] != 1
          ) return;
        
        A[i][j] = 2;
        dfs(A, i+1, j);
        dfs(A, i-1, j);
        dfs(A, i, j+1);
        dfs(A, i, j-1);
    }