Leetcode: Shortest Bridge

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. 1 <= A.length = A[0].length <= 100
  2. 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
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.