2021-07-28：最短的桥。在给定的二维二进制数组 A 中，存在两座岛。（岛是由四面相连的 1 形成的一个最大组。）现在，我们可以将 0 变为 1，以使两座岛连接起来，变成一座岛。返回必须翻转的 0 的最小数目。（可以保证答案至少是 1 。）
福大大 答案2021-07-28：
宽度优先遍历。找到第一个岛，广播一次，增加一层，碰到第二个岛为止。层数就是需要的返回值。
时间复杂度：O(NM)。
空间复杂度：O(NM)。
代码用golang编写。代码如下：
代码语言：txt复制package main
import (
"fmt"
"math"
)
func main() {
m := [][]int{{0, 1, 0}, {0, 0, 0}, {0, 0, 1}}
ret := shortestBridge(m)
fmt.Println(ret)
}
func shortestBridge(m [][]int) int {
N := len(m)
M := len(m[0])
all := N * M
island := 0
curs := make([]int, all)
nexts := make([]int, all)
records := make([][]int, 2)
for i := 0; i < 2; i {
records[i] = make([]int, all)
}
for i := 0; i < N; i {
for j := 0; j < M; j {
if m[i][j] == 1 { // 当前位置发现了1！
// 把这一片的1，都变成2，同时，抓上来了，这一片1组成的初始队列
// curs, 把这一片的1到自己的距离，都设置成1了，records
queueSize := infect(m, i, j, N, M, curs, 0, records[island])
V := 1
for queueSize != 0 {
V
// curs里面的点，上下左右，records[点]==0， nexts
queueSize = bfs(N, M, all, V, curs, queueSize, nexts, records[island])
tmp := curs
curs = nexts
nexts = tmp
}
island
}
}
}
min := math.MaxInt64
for i := 0; i < all; i {
min = getMin(min, records[0][i] records[1][i])
}
return min - 3
}
func getMin(a int, b int) int {
if a < b {
return a
} else {
return b
}
}
// 当前来到m[i][j] , 总行数是N，总列数是M
// m[i][j]感染出去(找到这一片岛所有的1),把每一个1的坐标，放入到int[] curs队列！
// 1 (a,b) -> curs[index ] = (a * M b)
// 1 (c,d) -> curs[index ] = (c * M d)
// 二维已经变成一维了， 1 (a,b) -> a * M b
// 设置距离record[a * M b ] = 1
func infect(m [][]int, i int, j int, N int, M int, curs []int, index int, record []int) int {
if i < 0 || i == N || j < 0 || j == M || m[i][j] != 1 {
return index
}
// m[i][j] 不越界，且m[i][j] == 1
m[i][j] = 2
p := i*M j
record[p] = 1
// 收集到不同的1
curs[index] = p
index
index = infect(m, i-1, j, N, M, curs, index, record)
index = infect(m, i 1, j, N, M, curs, index, record)
index = infect(m, i, j-1, N, M, curs, index, record)
index = infect(m, i, j 1, N, M, curs, index, record)
return index
}
// 二维原始矩阵中，N总行数，M总列数
// all 总 all = N * M
// V 要生成的是第几层 curs V-1 nexts V
// record里面拿距离
func bfs(N int, M int, all int, V int, curs []int, size int, nexts []int, record []int) int {
nexti := 0 // 我要生成的下一层队列成长到哪了？
for i := 0; i < size; i {
// curs[i] -> 一个位置
up := twoSelectOne(curs[i] < M, -1, curs[i]-M)
down := twoSelectOne(curs[i] M >= all, -1, curs[i] M)
left := twoSelectOne(curs[i]%M == 0, -1, curs[i]-1)
right := twoSelectOne(curs[i]%M == M-1, -1, curs[i] 1)
if up != -1 && record[up] == 0 {
record[up] = V
nexts[nexti] = up
nexti
}
if down != -1 && record[down] == 0 {
record[down] = V
nexts[nexti] = down
nexti
}
if left != -1 && record[left] == 0 {
record[left] = V
nexts[nexti] = left
nexti
}
if right != -1 && record[right] == 0 {
record[right] = V
nexts[nexti] = right
nexti
}
}
return nexti
}
func twoSelectOne(c bool, a int, b int) int {
if c {
return a
} else {
return b
}
}执行结果如下：
图片左神java代码
