力扣-934. 最短的桥

题目描述

思路及实现

看题，想都不用想迷宫问题直接bfs或者dfs完事了好吧（
可能题目描述不是很好，在这里简单描述一下，岛是这样定义的：相连的1。也就是一个1，它的四个方向如果某个方向有1，那么这些1算一个岛，如果没有，那它本身就是一个岛。
所以，为了防止我们搭桥搭到本岛，我们需要先把第一个岛找出来：首先直接遍历，直到找到是一个是1的位置（代表陆地的位置），然后用dfs或者bfs把所有相邻的1找出来，下面代码我用的是迭代实现的dfs。
找完一个岛之后，我们就开始搭桥了。这里需要用到bfs，因为需要搭一个最短的桥，bfs可以每次往外扩一圈。
但是这里需要对bfs进行一点修改，采用的是这样的策略：我们把当前踩的地方利用bfs遍历完，这才代表往外扩大一圈，桥长度加一，然后这次遍历新找到的地方存放在一个新队列，用于下次扩圈。当然如果bfs过程中找到1（陆地）了，就直接返回桥的长度。

class Solution:
    def shortestBridge(self, grid: List[List[int]]) -> int:
        n = len(grid)  # 构建标记二维数组，0和1都表示unvisited，-1表示visited
        a_stack = deque()  # dfs用的栈
        a_queue = deque()  # bfs用的队列
        step = 0  # 桥的长度(必须翻转的0的最小数目)
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:  # 先找第一个岛
                    grid[i][j] = -1
                    a_stack.append((i, j))
                    a_queue.append((i, j))
                    break
            if a_stack:
                break
        while a_stack:  # dfs把第一个岛的范围找出来
            i, j = a_stack.pop()
            for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):  # 上下左右找
                if 0 <= x < n and 0 <= y < n and grid[x][y] == 1:  # 如果unvisited而且是陆地
                    grid[x][y] = -1  # 标记visited
                    a_stack.append((x, y))  # 入栈
                    a_queue.append((x, y))  # 入队
        while True:  # bfs搭桥
            tmp = a_queue
            a_queue = deque()
            for i, j in tmp:
                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):  # 上下左右找
                    if 0 <= x < n and 0 <= y < n:
                        if grid[x][y] == 0:  # 如果unvisited而且是陆地
                            grid[x][y] = -1  # 标记visited
                            a_queue.append((x, y))  # 入队
                        elif grid[x][y] == 1:  # 找到下一座岛
                            return step
            step += 1  # 每往外找一圈桥的长度就加一

---

希望本文章能够帮到您~