leetcode-1129颜色交替的最短路径

Posted on Edited on In

1129颜色交替的最短路径

rHfotA.jpg

重点在于有红边和蓝边两种颜色, 使用不同的方法要考虑不同的情况

BFS

可以使用BFS, 从0点出发不断加入后续节点, 常规的BFS可能访问一个节点后就不再访问, 在该题中却不同. (to_v_color, v)代表到v节点的to_v_color颜色路径, 如果访问了(RED, v), 则不能再次访问(RED, v), 但是可以访问(BLUE, v).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
RED, BLUE = -1, 1
class Solution:
    def shortestAlternatingPaths(self, n, red_edges, blue_edges: List[List[int]]) -> List[int]:
        # 构造邻接表, 同时记录路径颜色
        graph = [[] for _ in range(n)]
        for edge in red_edges:
            graph[edge[0]].append((RED, edge[1]))
        for edge in blue_edges:
            graph[edge[0]].append((BLUE, edge[1]))
        ans = [-1] * n
        visited = set()
        length = 0
        d = deque()
        # 初始化队列, (RED, 0), (BLUE, 0)已经访问, 不能再从其他节点到0节点
        d.append((RED, 0))
        d.append((BLUE, 0))
        visited.add((RED, 0))
        visited.add((BLUE, 0))
        while len(d) != 0:
            # 访问该层节点
            for _ in range(len(d)):
                to_v_color, v = d.popleft()
                if ans[v] == -1:
                    # 第一次访问v
                    ans[v] = length
                else:
                    # 可能有(RED, v)(visited)和(BLUE, v)(not visited)
                    # 取两种路径最小值
                    ans[v] = min(ans[v], length)
                # 加入next nodes
                for color, n in graph[v]:
                    # 只访问red, blue交替路径 && (color, n)没有访问过
                    if to_v_color + color == 0 and (color, n) not in visited:
                        visited.add((color, n))
                        d.append((color, n))
            length += 1
        return ans

DFS

在BFS中访问节点, 有默认的顺序, 如果访问了(RED, v), 在之后又访问了(RED, v), 则第二次访问肯定比第一次路径长, 因为BFS按照层级访问. 在DFS中, 如果第一次访问(RED, v) length0, 之后访问(RED, v) length1, 如果length1 >= length0, 则第二次不用访问

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
RED, BLUE = -1, 1
class Solution:
    def __init__(self):
        self.graph = None
        self.ans = None
        self.stack = set()      # 当前访问路径上的边
        self.visited = {}       # 所有已经访问过的边

    def shortestAlternatingPaths(self, n, red_edges, blue_edges: List[List[int]]) -> List[int]:
        # 构造邻接矩阵
        self.graph = [[] for _ in range(n)]
        for edge in red_edges:
            self.graph[edge[0]].append((RED, edge[1]))
        for edge in blue_edges:
            self.graph[edge[0]].append((BLUE, edge[1]))
        self.ans = [-1] * n
        self.dfs(0, RED, 0)
        self.dfs(0, BLUE, 0)
        return self.ans

    def dfs(self, v, to_v_color, length):
        k = (to_v_color, v)
        # 如果(to_v_color, v)已经访问过, 并且本次length大于上次访问时的length, 则不必再次访问
        if k in self.visited and length >= self.visited[k]:
            return
        # 记录使用to_v_color访问v节点时的length
        self.visited[k] = length
        self.stack.add(k)
        if self.ans[v] == -1:
            self.ans[v] = length
        else:
            self.ans[v] = min(self.ans[v], length)
        for color, n in self.graph[v]:
            # 访问red, blue交替节点 && (color, n)不在当前访问路径上
            if color + to_v_color == 0 and (color, n) not in self.stack:
                self.dfs(n, color, length + 1)
        self.stack.remove(k)