934. 最短的桥.md

934. 最短的桥

题目传送门

点击这里

解题思路

这道题使用的是bfs，首先看题意可以理解成找到两个完整岛屿之间的最短距离，我们可以先通过bfs找到其中完整的一座岛，然后对该岛上的每一块陆地的四个方向都进行bfs，算做一次，只考虑遇见水域和陆地的情况，遇见水域或者同岛屿的陆地，则记录遍历后继续，遇到零一做到的陆地则直接返回。同样在获取某一个岛屿的全部陆地可以用dfs的方法。

代码

var dir = [][]int{
    {-1, 0},
    {0, -1},
    {1, 0},
    {0, 1},
}

func shortestBridge(grid [][]int) int {
    var res int
    // 这类题型都最好把x和y作为统一的一个结构来使用
    type pair struct {
        x int
        y int
    }
    n := len(grid)
    // 先遍历整个grid，找到其中一个岛
    for i, r := range grid {
        for j, v := range r {
            if v != 1 {
                continue
            }
            group := []pair{}
            // 遍历过的地方置为-1
            grid[i][j] = -1
            q := []pair{{i, j}}
            // bfs模板
            for len(q) > 0 {
                p := q[0]
                q = q[1:]
                group = append(group, p)
                for _, d := range dir {
                    nx, ny := p.x+d[0], p.y+d[1]
                    if 0 <= nx && nx < n && 0 <= ny && ny < n && grid[nx][ny] == 1 {
                        grid[nx][ny] = -1
                        q = append(q, pair{nx, ny})
                    }
                }
            }
            // 添加完的group是某一个岛的所有陆地，再从group进行广度遍历
            q = group
            for {
                tmp := q
                q = nil
                // 每一个陆地向四个方向都处理一次记为移动加一次。
                for _, p := range tmp {
                    for _, d := range dir {
                        nx, ny := p.x+d[0], p.y+d[1]
                        if  0 <= nx && nx < n && 0 <= ny && ny < n {
                            if grid[nx][ny] == 1 {
                                return res
                            }
                            // 将周围的水域置为陆地，添加到bfs的遍历中
                            if grid[nx][ny] == 0 {
                                grid[nx][ny] = -1
                                q = append(q, pair{nx, ny})
                            }
                        }
                    }
                }
                res ++
            }
        }
    }
    return res
}

func shortestBridge(grid [][]int) (step int) {
    type pair struct{ x, y int }
    dirs := []pair{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
    n := len(grid)
    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
}