题目

在给定的二维二进制数组 A 中，存在两座岛。（岛是由四面相连的 1 形成的一个最大组。）

现在，我们可以将 0 变为 1，以使两座岛连接起来，变成一座岛。

返回必须翻转的 0 的最小数目。（可以保证答案至少是 1 。）

示例 1：输入：A = [[0,1],[1,0]] 输出：1

示例 2：输入：A = [[0,1,0],[0,0,0],[0,0,1]] 输出：2

示例 3：输入：A = [[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]] 输出：1

提示：2 <= A.length == A[0].length <= 100

A[i][j] == 0 或 A[i][j] == 1

解题思路分析

1、深度优先搜索+广度优先搜索；时间复杂度O(n^2)，空间复杂度O(n^2)

var dx = []int{0, 1, 0, -1}var dy = []int{1, 0, -1, 0}var queue [][2]intvar n intfunc shortestBridge(grid [][]int) int {   n = len(grid)   queue = make([][2]int, 0)   for i := 0; i < n; i++ {      for j := 0; j < n; j++ {         if grid[i][j] == 1 {            dfs(grid, i, j)  // 深度优先搜索找边界            return bfs(grid) // 广度优先搜索找距离         }      }   }   return 0}func dfs(grid [][]int, i, j int) {   if i < 0 || i >= n || j < 0 || j >= n {      return   }   if grid[i][j] == 0 {      queue = append(queue, [2]int{i, j}) // 加入边界   } else if grid[i][j] == 1 {      grid[i][j] = 2 // 标记为2      for k := 0; k < 4; k++ {         x, y := i+dx[k], j+dy[k]         dfs(grid, x, y)      }   }}func bfs(grid [][]int) int {   res := 0   for len(queue) > 0 {      res++      length := len(queue)      for i := 0; i < length; i++ {         a, b := queue[i][0], queue[i][1]         for j := 0; j < 4; j++ {            x, y := a+dx[j], b+dy[j]            if 0 <= x && x < n && 0 <= y && y < n {               if grid[x][y] == 2 {                  continue               }               if grid[x][y] == 1 {                  return res               }               queue = append(queue, [2]int{x, y})               grid[x][y] = 2            }         }      }      queue = queue[length:]   }   return res}

总结

Medium题目，先使用深度优先搜索找到边界的0，再使用广度优先搜索找到最短的路径