934. Shortest Bridge

Question:

In a given 2D binary array A, there are two islands. (An island is a 4-directionally connected group of 1s not connected to any other 1s.)

Now, we may change 0s to 1s so as to connect the two islands together to form 1 island.

Return the smallest number of 0s that must be flipped. (It is guaranteed that the answer is at least 1.)

Example 1:

Input: [[0,1],[1,0]]
Output: 1

Example 2:

Input: [[0,1,0],[0,0,0],[0,0,1]]
Output: 2

Example 3:

Input: [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
Output: 1

Note:

• 1 <= A.length = A[0].length <= 100
• A[i][j] == 0 or A[i][j] == 1

Solutions:

• Method 1: bfs + dfs
  • Use dfs to find a union region.
  • Use bfs to find the shortest path.

      class Solution {
      public int shortestBridge(int[][] A) {
          int startRow = 0, startCol = 0;
          int height = A.length, width = A[0].length;
          for(int i = 0; i < height; i++){
              for(int j = 0; j < width; j++){
                  if(A[i][j] == 1){
                      startRow = i;
                      startCol = j;
                      i = height;
                      break;
                  }
              }
          }
          dfs(A, startRow, startCol, height, width);
          LinkedList<int[]> queue = new LinkedList<>();
          int result = Integer.MAX_VALUE;
          for(int i = 0; i < height; i++){
              for(int j = 0; j < width; j++){
                  if(A[i][j] == 1){
                      result = Math.min(result, bfs(queue, i, j, A, height, width));
                  }
              }
          }
          return result;
      }		
      private void dfs(int[][] A, int i, int j, int height, int width, LinkedList<int[]> queue){
          A[i][j] = 2;
          int tempRow = 0, tempCol = 0;
          for(int d = 0; d < 4; d++){
              tempRow = i + dir[d][0];
              tempCol = j + dir[d][1];
              if(tempRow >= 0 && tempRow < height && tempCol >= 0 && tempCol < width && A[tempRow][tempCol] == 1){
                  queue.offer(new int[tempRow][tempCol]);
                  dfs(A, tempRow, tempCol, height, width);
              }
          }
      }
      private int bfs(LinkedList<int[]> queue, int row, int col, int[][] A, int height, int width){
          queue.clear();
          queue.offer(new int[]{row, col});
          int step = -1;
          boolean[][] visited = new boolean[height][width];
          visited[row][col] = true;
          while(!queue.isEmpty()){
              step++;
              int size = queue.size();
              for(int i = 0; i < size; i++){
                  int[] cur = queue.poll();
                  int tempRow = 0, tempCol = 0;
                  for(int d = 0; d < 4; d++){
                      tempRow = cur[0] + dir[d][0];
                      tempCol = cur[1] + dir[d][1];
                      if(tempRow >= 0 && tempRow < height && tempCol >= 0 && tempCol < width && !visited[tempRow][tempCol] && A[tempRow][tempCol] != 1){
                          if(A[tempRow][tempCol] == 2){
                              return step;
                          }
                          visited[tempRow][tempCol] = true;
                          queue.add(new int[]{tempRow, tempCol});
                      }
                  }
              }
          }
          return Integer.MAX_VALUE;
      }
      }
    

Reference

1. 花花酱 LeetCode 934. Shortest Bridge - 刷题找工作 EP230