<style>
html, body, .ui-content {
background: #222222;
color: #00BFFF;
}
::-webkit-scrollbar {
width: 10px;
}
::-webkit-scrollbar-track {
background: transparent;
}
::-webkit-scrollbar-thumb {
background: linear-gradient(180deg, #2BE8CF60 0%, #2B83E860 100%);
border-radius: 3px;
}
::-webkit-scrollbar-thumb:hover {
background: linear-gradient(180deg, #2BE8CF95 0%, #2B83E895 100%);
}
/* 設定 code 模板 */
.markdown-body code,
.markdown-body tt {
background-color: #ffffff36;
}
.markdown-body .highlight pre,
.markdown-body pre {
color: #ddd;
background-color: #00000036;
}
.hljs-tag {
color: #ddd;
}
.token.operator {
background-color: transparent;
}

</style>

###### tags: `Leetcode`

# 1129. Shortest Path with Alternating Colors

###### Link : https://leetcode.com/problems/shortest-path-with-alternating-colors/description/

## 題目
找到最短路徑，且路徑必須是藍色紅色交替的走
## 程式碼

enum color{Red = 0, Blue};
class Solution {
public:
    vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {
        vector<int> ans(n, -1);//ans預設皆-1
        vector<vector<int>> redAdj(n), blueAdj(n);
        for(auto &it : redEdges)//紅色的adjList
            redAdj[it[0]].push_back(it[1]);
        for(auto &it : blueEdges)//藍色的adjList
            blueAdj[it[0]].push_back(it[1]);
        BFS(ans, redAdj, blueAdj, Red);//紅色為開頭
        BFS(ans, redAdj, blueAdj, Blue);//藍色為開頭
        return ans;
    }
private:
    void BFS(vector<int> &ans, vector<vector<int>> redAdj, vector<vector<int>> blueAdj, color Color){
        queue<int> q;
        q.push(0);//起點為0
        int cnt = 0;//步數
        while(!q.empty()){
            int size = q.size();//第cnt步須從queue拿出多少
            for(int i = 0;i < size;++i){
                int cur = q.front(); q.pop();
                if(ans[cur] == -1 || ans[cur] > cnt)//如果沒走過或是這次的步數比較短
                    ans[cur] = cnt;//更新ans
                if(Color == Red){
                    for(int &it : redAdj[cur])
                        q.push(it);//所有可以走的路放進queue
                    redAdj[cur].clear();//走過的路刪掉
                }
                else{
                    for(int &it : blueAdj[cur])
                        q.push(it);//所有可以走的路放進queue
                    blueAdj[cur].clear();//走過的路刪掉
                }
            }
            ++cnt;
            size = q.size();//第cnt步須從queue拿出多少
            for(int i = 0;i < size;++i){
                int cur = q.front(); q.pop();
                if(ans[cur] == -1 || ans[cur] > cnt)//如果沒走過或是這次的步數比較短
                    ans[cur] = cnt;//更新ans
                if(Color == Red){
                    for(int &it : blueAdj[cur])
                        q.push(it);//所有可以走的路放進queue
                    blueAdj[cur].clear();//走過的路刪掉
                }
                else{
                    for(int &it : redAdj[cur])
                        q.push(it);//所有可以走的路放進queue
                    redAdj[cur].clear();//走過的路刪掉
                }
            }
            ++cnt;
        }
    }
};