934. Shortest Bridge.md

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 int[][] dir = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
   	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