【2022-10-25每日一题】934. 最短的桥[Medium]

2022-10-25每日一题：934. 最短的桥

难度：Medium

标签：深度优先搜索 、 广度优先搜索 、 数组 、 矩阵

给你一个大小为 n x n 的二元矩阵 grid ，其中 1 表示陆地，0 表示水域。

岛 是由四面相连的 1 形成的一个最大组，即不会与非组内的任何其他 1 相连。grid 中 恰好存在两座岛 。

示例 1：

输入：grid = [[0,1],[1,0]]
输出：1

示例 2：

输入：grid = [[0,1,0],[0,0,0],[0,0,1]]
输出：2

示例 3：

输入：grid = [[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

提示：

• n == grid.length == grid[i].length
• 2 <= n <= 100
• grid[i][j] 为 0 或 1
• grid 中恰有两个岛

方法一：深度优先搜索

详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读

type pair struct {x, y int}
func shortestBridge(grid [][]int) (step int) {
    n := len(grid)
    //                上，     右，     下，    左
    dirs := []pair{{-1, 0}, {0, 1}, {1, 0}, {0, -1}} // 四个方向
    for i, row := range grid {
        for j, v := range row {
            if v != 1 {
                continue
            }
            island := []pair{}
            grid[i][j] = -1
            // 广度优先搜索
            q := []pair{{i, j}}
            for len(q) > 0 {
                p := q[0]
                q = q[1:]
                island = append(island, p) // 记录组成第一个岛屿的所有点
                for _, d := range dirs {
                    x, y := p.x + d.x, p.y + d.y
                    if 0 <= x && x < n && 0 <= y && y < n && grid[x][y] == 1 {
                        grid[x][y] = -1
                        q = append(q, pair{x, y})
                    }
                }
            }
            // 从第一个岛屿的所有点，进行深度优先搜索找最短路径
            q = island
            for {
                tmp := q
                q = nil
                for _, p := range tmp {
                    for _, d := range dirs {
                        x, y := p.x+d.x, p.y+d.y
                        if 0 <= x && x < n && 0 <= y && y < n {
                            if grid[x][y] == 1 { // 找到第二个岛屿
                                return
                            }
                            if grid[x][y] == 0 {
                                grid[x][y] = -1
                                q = append(q, pair{x, y})
                            }
                        }
                    }
                }
                step++
            }
        }
    }
    return
}

复杂度分析

• 时间复杂度：O(n^2)，其中 n 表示 grid 的行数，grid 的行数与列数相等。我们只需遍历一遍矩阵即可完成访问两个不同的岛。

• 空间复杂度：O(n^2)。其中 nn 表示 grid 的行数，grid 的行数与列数相等。grid 中的岛含有的元素最多为 n^2个，广度优先搜索时队列中最多有 n^2个元素，因此空间复杂度为 O(n^2)。

方法二：深度优先搜索+广度优先搜索

type pair struct {x, y int}
func shortestBridge(grid [][]int) (step int) {
    n := len(grid)
    //                上，     右，     下，    左
    dirs := []pair{{-1, 0}, {0, 1}, {1, 0}, {0, -1}} // 四个方向
    for i, row := range grid {
        for j, v := range row {
            if v != 1 {
                continue
            }
            // 保存第一个岛屿的所有点
            q := []pair{}
            var dfs func(int, int)
            dfs = func(i, j int) {
            	grid[i][j] = -1
                q = append(q, pair{i, j}) // 记录组成第一个岛屿的所有点
                for _, d := range dirs {
                    x, y := i + d.x, j + d.y
                    if 0 <= x && x < n && 0 <= y && y < n && grid[x][y] == 1 {
                        dfs(x, y)
                    }
                }
            }
            dfs(i, j)
            
            for {
                tmp := q
                q = nil
                for _, p := range tmp {
                    for _, d := range dirs {
                        x, y := p.x+d.x, p.y+d.y
                        if 0 <= x && x < n && 0 <= y && y < n {
                            if grid[x][y] == 1 { // 找到第二个岛屿
                                return
                            }
                            if grid[x][y] == 0 {
                                grid[x][y] = -1
                                q = append(q, pair{x, y})
                            }
                        }
                    }
                }
                step++
            }
        }
    }
    return
}

复杂度分析同上

LeetCode题库地址

• https://leetcode.cn/problems/shortest-bridge