Shortest Bridge

Similar Problems:

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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

- Solution:

// Blog link: https://code.dennyzhang.com/shortest-bridge // Basic Ideas: BFS // Complexity: Time O(n), Space O(n) func shortestBridge(A [][]int) int { res := 0 queue := [][]int{} offsets := [][]int{[]int{0, 1}, []int{0, -1}, []int{1, 0}, []int{-1, 0}} for i, row := range A { for j, value := range row { if value == 1 { queue = append(queue, []int{i, j}) A[i][j] = 2 // mark current region as 2 border := [][]int{} for len(queue) != 0 { l := [][]int{} for _, point := range queue { for _, offset := range offsets { i2, j2 := point[0]+offset[0], point[1]+offset[1] if i2<0 || i2>=len(A) || j2<0 || j2>=len(A[0]) || A[i2][j2] == 2 { continue } if A[i2][j2] == 0 { border = append(border, []int{i2, j2}) } else { A[i2][j2] = 2 l = append(l, []int{i2, j2}) } } } queue = l } queue = border break } } if len(queue) != 0 { break } } // start bfs for len(queue) != 0 { res++ l := [][]int{} for _, point := range queue { for _, offset := range offsets { i2, j2 := point[0]+offset[0], point[1]+offset[1] if i2<0 || i2>=len(A) || j2<0 || j2>=len(A[0]) || A[i2][j2] == 2 { continue } if A[i2][j2] == 1 { return res } else { l = append(l, []int{i2, j2}) A[i2][j2] = 2 } } } queue = l } return res+1 }

Share It, If You Like It.