934. Shortest Bridge

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

solution

• 第一步标记岛屿一, 第二步bfs, 岛屿一的位置作为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()

follow up

1976. Number of Ways to Arrive at Destination

class Solution:
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
        # ways[i] 从0到第i个节点的最短路径个数
        # dist[i] 从0到第i个节点的最短路径

        graph = collections.defaultdict(list)
        for u, v, time in roads:
            graph[u].append([v, time])
            graph[v].append([u, time])

        return self.dijkstra(0, n, graph)

    def dijkstra(self, src, n, graph):
        dist = [float('inf')] * n
        ways = [0] * n

        dist[src] = 0
        ways[src] = 1
        heap = [(0, src)]  # dist, src

        while heap:
            d, u = heapq.heappop(heap)
            if dist[u] < d:
                continue

            for v, time in graph[u]:
                if dist[v] > d + time:
                    dist[v] = d + time
                    ways[v] = ways[u]
                    heapq.heappush(heap, (dist[v], v))
                elif dist[v] == d + time:
                    ways[v] = (ways[v] + ways[u]) % 1_000_000_007
        return ways[n-1]