LeetCode 1129. 颜色交替的最短路径

2024-03-20 HGNULB 约 11 分钟

文章信息 7 个分类 2 个标签

分类

题目描述

✅ 1129. 颜色交替的最短路径

题意分析

给一张 n 个节点的有向图，边分红蓝两色，要对每个节点 i 求出「从节点 0 到 i 且路径上红蓝边严格交替」的最短长度，不可达则记 -1。

「严格交替」这条约束把问题从普通最短路里拆了出来：能不能走某条边，不只取决于站在哪个节点，还取决于上一步踩的是什么颜色。这说明单纯以节点为单位记录访问状态是不够的，同一个节点在「刚走过红边到达」和「刚走过蓝边到达」这两种情形下，后续可走的边完全不同。

所有边权都是 1，求的是最短步数，这两点合起来是广度优先搜索的典型信号——不需要优先队列，队列的先进先出顺序自然就是距离递增顺序。

边界包括：节点 0 到自身距离恒为 0；图里允许自环和重边，所以必须靠访问标记防止无限扩展；某些节点可能任何交替路径都到不了，要输出 -1。

解法：带颜色状态的广度优先搜索

核心思路

先看朴素做法为什么不行。若直接用「节点」做 BFS 的访问标记，第一次到达某节点就把它永久标记掉，那么后面通过另一种颜色到达同一节点的路径会被剪掉。但被剪掉的那条路径可能虽然更长，却因为末边颜色不同而能继续往下走，剪错就会漏解。

瓶颈在于状态定义粒度太粗。观察「能否继续前进」这个判定所依赖的信息，恰好是「当前在哪个节点」加上「上一条边是什么颜色」两项——再多的历史（走了哪些点、怎么绕过来的）都不影响未来。于是把状态从「节点」升级成二元组「(节点, 上一条边颜色)」，图就从 n 个状态变成 2n 个状态，而交替约束在新图上退化成普通的邻接关系：状态 (u, c) 只能沿颜色为 1 - c 的边走到 (v, 1 - c)。

起点需要特殊处理：从节点 0 出发时并没有「上一条边」，下一步红蓝都能走。把 (0, 红) 和 (0, 蓝) 两个状态同时置为距离 0 并入队即可——它们表示「假装上一条边是红/蓝」，从而分别放行蓝色和红色的第一步，合起来正是「两种颜色都允许」。

由此得到 BFS 维护的不变量：队列中状态的距离值单调不减，且一个状态第一次被赋值时的距离就是它的最短距离。因为所有边权都是 1，队列按层推进，先出队的状态距离一定不大于后出队的；一个状态被首次发现时，产生它的那条路径必然是最短的，之后再遇到只会更长，可以安全跳过。

最后把每个节点的两种状态取较小的非 -1 值合并，就是该节点的答案。

解题步骤

按颜色分别建两张邻接表 graph[0] 存红边、graph[1] 存蓝边。分开存是为了在扩展时能直接按需要的颜色取出邻居，而不必对每条边再判一次颜色。

开二维数组 dist[n][2] 并全部填 -1。-1 同时表示「尚未访问」和「不可达」，一个值承担两种语义是安全的，因为真实距离恒为非负。

把 dist[0][0] 和 dist[0][1] 都置为 0，并把两个状态一起入队。这就是多源起点的写法，它让第一步红蓝皆可走，而不需要为「起点无上一条边」单独定义第三种颜色。

循环弹出状态 (node, lastColor)，算出本步允许的颜色 nextColor = 1 - lastColor。这一行是交替约束的全部实现——只从异色邻接表里取邻居，非法的同色转移根本不会被生成。

对每个邻居 next，若 dist[next][nextColor] 已被赋值就跳过，否则置为 dist[node][lastColor] + 1 并入队。标记必须在入队时立刻写，而不是出队时才写，否则同一状态可能被多条路径重复入队，队列规模会退化。

BFS 结束后逐个节点合并两种颜色的距离：都为 -1 则答案是 -1，只有一个有效就取它，两个都有效取较小值。

以 n = 3、redEdges = [[0,1],[1,2]]、blueEdges = [] 走一遍。红邻接表是 graph[0][0] = [1]、graph[0][1] = [2]，蓝邻接表全空。dist 初始为 [[-1,-1],[-1,-1],[-1,-1]]，随后 dist[0] = [0,0]，队列为 [(0,红), (0,蓝)]。

弹出 (0, 红)：上一条是红，本步只能走蓝，而蓝邻接表里节点 0 没有出边，什么都不做。这一步很关键——它体现了状态拆分的意义：站在同一个节点 0 上，「上一条是红」这个状态是走不动的。

弹出 (0, 蓝)：本步走红，取出邻居 1。dist[1][红] 还是 -1，置为 dist[0][蓝] + 1 = 1，把 (1, 红) 入队。

弹出 (1, 红)：本步只能走蓝，蓝邻接表里节点 1 没有出边，无法扩展。队列空，BFS 结束。

合并结果：节点 0 的两个状态都是 0，答案 0；节点 1 是 [1, -1]，取 1；节点 2 是 [-1, -1]，答案 -1。最终返回 [0, 1, -1]。

这个用例正好说明了交替约束的威力：图上明明存在 0 → 1 → 2 的路径，但两条边同为红色，不满足交替，所以节点 2 不可达。

代码实现

class Solution {
    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        java.util.List<Integer>[][] graph = new java.util.ArrayList[2][n];
        for (int color = 0; color < 2; color++) {
            for (int i = 0; i < n; i++) {
                graph[color][i] = new java.util.ArrayList<>();
            }
        }

        for (int[] edge : redEdges) {
            graph[0][edge[0]].add(edge[1]);
        }
        for (int[] edge : blueEdges) {
            graph[1][edge[0]].add(edge[1]);
        }

        int[][] dist = new int[n][2];
        for (int i = 0; i < n; i++) {
            java.util.Arrays.fill(dist[i], -1);
        }

        java.util.Queue<int[]> queue = new java.util.ArrayDeque<>();
        dist[0][0] = 0;
        dist[0][1] = 0;
        queue.offer(new int[] {0, 0});
        queue.offer(new int[] {0, 1});

        while (!queue.isEmpty()) {
            int[] state = queue.poll();
            int node = state[0];
            int lastColor = state[1];
            int nextColor = 1 - lastColor;

            for (int next : graph[nextColor][node]) {
                if (dist[next][nextColor] != -1) {
                    continue;
                }
                dist[next][nextColor] = dist[node][lastColor] + 1;
                queue.offer(new int[] {next, nextColor});
            }
        }

        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            if (dist[i][0] == -1) {
                answer[i] = dist[i][1];
            } else if (dist[i][1] == -1) {
                answer[i] = dist[i][0];
            } else {
                answer[i] = Math.min(dist[i][0], dist[i][1]);
            }
        }

        return answer;
    }
}

func shortestAlternatingPaths(n int, redEdges [][]int, blueEdges [][]int) []int {
    graph := make([][][]int, 2)
    for color := 0; color < 2; color++ {
        graph[color] = make([][]int, n)
    }

    for _, edge := range redEdges {
        graph[0][edge[0]] = append(graph[0][edge[0]], edge[1])
    }
    for _, edge := range blueEdges {
        graph[1][edge[0]] = append(graph[1][edge[0]], edge[1])
    }

    dist := make([][2]int, n)
    for i := 0; i < n; i++ {
        dist[i] = [2]int{-1, -1}
    }

    queue := [][2]int{{0, 0}, {0, 1}}
    dist[0][0] = 0
    dist[0][1] = 0

    for head := 0; head < len(queue); head++ {
        state := queue[head]
        node := state[0]
        lastColor := state[1]
        nextColor := 1 - lastColor

        for _, next := range graph[nextColor][node] {
            if dist[next][nextColor] != -1 {
                continue
            }
            dist[next][nextColor] = dist[node][lastColor] + 1
            queue = append(queue, [2]int{next, nextColor})
        }
    }

    answer := make([]int, n)
    for i := 0; i < n; i++ {
        redDist := dist[i][0]
        blueDist := dist[i][1]
        if redDist == -1 {
            answer[i] = blueDist
        } else if blueDist == -1 {
            answer[i] = redDist
        } else if redDist < blueDist {
            answer[i] = redDist
        } else {
            answer[i] = blueDist
        }
    }

    return answer
}

复杂度分析

时间复杂度：$O(n + r + b)$，r、b 分别是红蓝边数。状态总数是 2n，每个状态只入队出队一次；每条边最多在两种颜色状态下各被检查一次，总扩展量与边数同阶。

空间复杂度：$O(n + r + b)$，邻接表要存下全部边，dist 数组和队列各占 $O(n)$；若只按节点数衡量辅助结构则是 $O(n)$。

关键点总结

当「能否走下一步」依赖的信息超出「当前在哪」时，把额外信息塞进状态里，问题就退化成新图上的普通最短路——这就是分层图/状态扩展，通用套路是「原状态 × 附加维度」。

判断附加维度该取什么，标准是「最小充分统计量」：只保留影响未来决策的信息（这里是上一条边的颜色），历史路径的其余部分一律丢掉，否则状态数会爆炸。

边权全为 1 时用 BFS 而不是 Dijkstra，队列的天然层序就保证了首次到达即最短，省掉堆的对数因子。

访问标记必须在入队瞬间打上，出队时再打会让同一状态被重复入队，最坏情况下队列规模膨胀到边数级别。

起点没有「上一步」时，把所有等价的初始状态一起入队（这里是 (0,红) 和 (0,蓝)），比新增一种「无颜色」状态更简洁，也避免了在扩展逻辑里加特判。

面试视角：面试官想听的是「为什么不能只用节点做 visited」，你要能当场给出反例——一条较长但末边颜色合适的路径被剪掉后答案变错。答完主解法可以补一句：这类题都可以统一表述成「在状态图上跑 BFS」，1345、1654、1293 全是同一个模板换个附加维度。

易错点总结

错误写法：用一维 visited[node] 而不是 dist[node][color] 做访问标记 → 用例 n = 3, redEdges = [[0,1]], blueEdges = [[1,2],[0,2]]，节点 2 先被 (0→2 蓝) 标记为 1 之后，经由红边到 1 再走蓝边的路径被整体剪掉，某些更复杂的图上会把本可达的节点判成 -1。

错误写法：只把 (0, 红) 一个状态入队 → 用例 n = 3, redEdges = [[0,1],[1,2]], blueEdges = []，第一步被限死为蓝色，节点 1 也变成不可达，返回 [0,-1,-1]，正确答案是 [0,1,-1]。

错误写法：扩展时用 graph[lastColor] 而不是 graph[1 - lastColor] → 用例同上，走的是同色边，交替约束彻底失效，返回 [0,1,2]。

错误写法：把 dist[0][0] 和 dist[0][1] 初始化成 -1 只入队不赋值 → 用例任意，扩展时 dist[node][lastColor] + 1 读到 -1，第一层邻居的距离被算成 0，整张距离表偏移一位。

错误写法：出队时才标记已访问 → 用例中存在多条路径指向同一状态的图，同一状态被反复入队，队列规模膨胀到边数级，大数据下超时。

错误写法：合并答案时直接写 Math.min(dist[i][0], dist[i][1]) 不判 -1 → 用例 n = 3, redEdges = [[0,1],[1,2]], blueEdges = []，节点 1 的两个值是 1 和 -1，取最小得 -1，正确答案是 1。

错误写法：把边当成无向边，两个方向都建 → 用例 n = 2, redEdges = [[1,0]], blueEdges = []，节点 1 到 0 的边被反向复制，节点 1 被误判为距离 1，正确答案是 -1。

错误写法：忽略自环，认为自环无害而不做访问判断 → 用例 redEdges = [[0,0]], blueEdges = [[0,0]]，(0,红) 与 (0,蓝) 互相扩展，若没有 dist 判重会无限入队直到内存耗尽。

错误写法：用 DFS 递归代替 BFS 求最短路 → 用例 n = 4, redEdges = [[0,1],[0,2]], blueEdges = [[1,3],[2,3]]，DFS 先找到的路径不一定最短，若不做完整搜索与松弛就会输出偏大的距离。

错误写法：建图时用 edge[1] 作为起点、edge[0] 作为终点 → 用例 n = 2, redEdges = [[0,1]], blueEdges = []，方向反了，节点 1 被判成不可达返回 -1，正确答案是 1。

错误写法：answer 数组忘记给节点 0 赋值或写死为 -1 → 用例任意，节点 0 到自身距离恒为 0，输出 -1 直接判错。

相似题目

题目	难度	考察点
127. 单词接龙	困难	状态是字符串，边靠改一个字母隐式生成，需预处理通配桶加速
433. 最小基因变化	中等	字符集只有四种，可直接枚举变异并用集合校验合法性
542. 01 矩阵	中等	多源起点，从所有 0 同时扩散求每格最近距离
752. 打开转盘锁	中等	状态是四位密码，需处理死亡列表并可用双向 BFS 优化
773. 滑动谜题	困难	状态要把棋盘序列化成字符串，转移由空格位置决定
854. 相似度为 K 的字符串	困难	转移是交换两个字符，需要剪枝只交换能立刻归位的字符
909. 蛇梯棋	中等	编号与坐标之间要做蛇形换算，落点可能被梯子直接改写
994. 腐烂的橘子	中等	多源扩散求整体耗时，还要判断是否存在永远腐烂不到的格子
1091. 二进制矩阵中的最短路径	中等	八连通方向，起点终点本身可能就是障碍
1162. 地图分析	中等	同样多源扩散，但答案取的是所有距离里的最大值
1293. 网格中的最短路径	困难	附加维度是剩余可消除障碍数，与本题的颜色维度是同一套扩展手法
1298. 你能从盒子里获得的最大糖果数	困难	队列里要维护待处理的盒子与钥匙，解锁关系导致节点可延迟可达
1345. 跳跃游戏 IV	困难	同值下标互相连边，必须在用过一次后清空该值的桶防止重复扩展
1654. 到家的最少跳跃次数	中等	附加维度是「上一步是否后退」，与本题的颜色交替结构几乎一致
LCP 09. 最小跳跃次数	困难	需要维护已扩展的最右边界，避免向左弹射时重复入队
LCR 107. 01 矩阵	中等	542 的中文版，可对照多源 BFS 与两遍 DP 两种解法
LCR 108. 单词接龙	困难	127 的中文版，适合练双向 BFS 的写法
LCR 109. 打开转盘锁	中等	752 的中文版，重点是把起点即死亡状态的特判想全