1129. Shortest Path with Alternating Colors ⭐

Medium

You are given an integer n, the number of nodes in a directed graph where the nodes are labeled from 0 to n - 1. Each edge is red or blue in this graph, and there could be self-edges and parallel edges.

You are given two arrays redEdges and blueEdges where:

• redEdges[i] = [ai, bi] indicates that there is a directed red edge from node ai to node bi in the graph, and

• blueEdges[j] = [uj, vj] indicates that there is a directed blue edge from node uj to node vj in the graph.

Return an array answer of length n, where each answer[x] is the length of the shortest path from node 0 to node x such that the edge colors alternate along the path, or -1 if such a path does not exist.

Example 1:

Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
Output: [0,1,-1]

Example 2:

Input: n = 3, redEdges = [[0,1]], blueEdges = [[2,1]]
Output: [0,1,-1]

Constraints:

• 1 <= n <= 100

• 0 <= redEdges.length, blueEdges.length <= 400

• redEdges[i].length == blueEdges[j].length == 2

• 0 <= ai, bi, uj, vj < n

解題

func shortestAlternatingPaths(n int, red_edges [][]int, blue_edges [][]int) []int {
    // red[0] 會紀錄 node0 有通往哪些其他節點的紅邊
    // blue[0] 會紀錄 node0 有通往哪些其他節點的藍邊
    red := make([][]int, n) 
    blue := make([][]int, n) 
    
    for _, edge := range red_edges {
        red[edge[0]] = append(red[edge[0]], edge[1])
    }

    for _, edge := range blue_edges {
        blue[edge[0]] = append(blue[edge[0]], edge[1])
    }
    
    // BFS，queue 存放 這一層 level 要訪問的節點
    queue := make([][]int, 0)
    queue = append(queue, []int{0, -1}) // 從節點0出發，邊用 -1 特別記錄
    // res 記錄 0 到每個點的最短路徑，初始化為 -1，不可到達
    res := make([]int, n)
    for i := 0; i < n; i ++{
        res[i] = -1
    }
    
    // 記錄是否從紅藍邊通往某一點過
    // 例如：已經從紅邊訪問過節點3，那下次要從紅邊訪問節點3，路徑長必定大於之前紀錄的值，可以跳過
    visited := make([][]bool, n)
    for j := 0; j < n; j ++{
        visited[j] = []bool{false, false}
    }
    
    // level，也就是目前路境長
    level := 0
    
    // 沒有節點需要拜訪才跳出迴圈
    for len(queue) != 0 {
        next := [][]int{} // 下一層要遞迴的點
        for _, n := range queue { //遞迴拜訪這一層的點
            label := n[0] // 這個點的label
            color := n[1] // 這個點的顏色

            if color != -1 { 
                visited[label][color] = true // 其他點從紅邊或藍邊訪問過這個點了
            }
            // 第一次到這個點，目前是最短路徑！記錄起來
            if res[label] == -1 {
                res[label] = level
            }
            
            // 目前是藍色(color=0)或是在節點0，把紅色的邊與要去的點加到下一層要訪問的陣列中
            if color == 0 || color == -1 {
                for _, neighbor := range red[label] {
                    if !visited[neighbor][1] {
                        next = append(next, []int{neighbor, 1})
                    }
                }
            }
            
            // 目前是紅色(color=1)或是在節點0，把藍色的邊與要去的點加到下一層要訪問的陣列中
            if color == 1 || color == -1 {
                for _, neighbor := range blue[label] {
                    if !visited[neighbor][0] {
                        next = append(next, []int{neighbor, 0})
                    }
                }
            }
        }

        queue = next // 待會要訪問下一層了！
        level++ // 層數 == 路徑長 加1
    }

    return res
}