934. Shortest Bridge

https://leetcode.com/problems/shortest-bridge/

solution

• 第一步标记岛屿一, 并且岛屿一的位置作为第二步bfs的起始队列

class Solution:
    def __init__(self):
        self.dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    
    def shortestBridge(self, grid: List[List[int]]) -> int:
        n = len(grid)
        visited = [[False] * n for _ in range(n)]
        # queue = collections.deque([[i, j, step]])  # 注意两层[]
        queue = collections.deque()

        # step 1: 其中一个岛屿改为2，以区别两个岛屿
        for i in range(n):
            if queue:
                break
            for j in range(n):
                if grid[i][j] == 1 and visited[i][j] == False:                    
                    self.dfs(grid, i, j, visited, queue)               
                if queue:
                    break  # 注意break位置, 感觉需要进一步优化  
      
        # step 2: BFS连接两个岛屿
        step = 0
        while queue:
            for _ in range(len(queue)):
                x, y = queue.popleft()
                for move in self.dirs:
                    new_i = x + move[0]
                    new_j = y + move[1]

                    if 0 <= new_i < len(grid) and 0 <= new_j < len(grid[0]) and visited[new_i][new_j] == False:
                        if grid[new_i][new_j] == 1:
                            return step
                        queue.append([new_i, new_j])
                        visited[new_i][new_j] = True
            step += 1
    
    def dfs(self, grid, i, j, visited, queue):        
        grid[i][j] = 2
        visited[i][j] = True
        queue.append([i, j])

        for move in self.dirs:
            new_i = i + move[0]
            new_j = j + move[1]

            if 0 <= new_i < len(grid) and 0 <= new_j < len(grid[0]) and visited[new_i][new_j] == False and grid[new_i][new_j] == 1:
                self.dfs(grid, new_i, new_j, visited, queue)        

时间复杂度：O() 空间复杂度：O()