# 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
}
```

Share It, If You Like It.