生活随笔
收集整理的這篇文章主要介紹了
LeetCode 1129. 颜色交替的最短路径（BFS）
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
文章目錄
1. 題目
在一個有向圖中，節(jié)點分別標(biāo)記為 0, 1, ..., n-1。
這個圖中的每條邊不是紅色就是藍色，且存在自環(huán)或平行邊。
red_edges 中的每一個 [i, j] 對表示從節(jié)點 i 到節(jié)點 j 的紅色有向邊。
類似地，blue_edges 中的每一個 [i, j] 對表示從節(jié)點 i 到節(jié)點 j 的藍色有向邊。
返回長度為 n 的數(shù)組 answer，其中 answer[X] 是從節(jié)點 0 到節(jié)點 X 的紅色邊和藍色邊交替出現(xiàn)的最短路徑的長度。
如果不存在這樣的路徑，那么 answer[x] = -1。
示例
1：
輸入：n
= 3, red_edges
= [[0,1],[1,2]], blue_edges
= []
輸出：
[0,1,-1]示例
2：
輸入：n
= 3, red_edges
= [[0,1]], blue_edges
= [[2,1]]
輸出：
[0,1,-1]示例
3：
輸入：n
= 3, red_edges
= [[1,0]], blue_edges
= [[2,1]]
輸出：
[0,-1,-1]示例
4：
輸入：n
= 3, red_edges
= [[0,1]], blue_edges
= [[1,2]]
輸出：
[0,1,2]示例
5：
輸入：n
= 3, red_edges
= [[0,1],[0,2]], blue_edges
= [[1,0]]
輸出：
[0,1,1]提示：
1 <= n
<= 100
red_edges
.length
<= 400
blue_edges
.length
<= 400
red_edges
[i
].length
== blue_edges
[i
].length
== 2
0 <= red_edges
[i
][j
], blue_edges
[i
][j
] < n
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/shortest-path-with-alternating-colors
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
2. 解題
- 分兩種情況從 0 出發(fā)，紅色，或者藍色
- 每個點的訪問標(biāo)記 vis 有 2 個狀態(tài)（紅的訪問沒？藍的訪問沒？）
class Solution {
public:vector
<int> shortestAlternatingPaths(int n
, vector
<vector
<int>>& red_edges
, vector
<vector
<int>>& blue_edges
) {vector
<vector
<int>> dis(2, vector
<int>(n
, INT_MAX
));vector
<vector
<int>> r(n
), b(n
);for(auto& e
: red_edges
)r
[e
[0]].push_back(e
[1]);for(auto& e
: blue_edges
)b
[e
[0]].push_back(e
[1]);bfs(r
,b
,0,dis
);bfs(r
,b
,1,dis
);vector
<int> ans(n
,-1);for(int i
= 0; i
< n
; ++i
){ans
[i
] = min(dis
[0][i
], dis
[1][i
]);if(ans
[i
] == INT_MAX
)ans
[i
] = -1;}return ans
;}void bfs(vector
<vector
<int>>& r
, vector
<vector
<int>>& b
, int flag
, vector
<vector
<int>>& dis
){int n
= r
.size(), cur
, size
, step
= 0;vector
<vector
<bool>> vis(2, vector
<bool>(n
, false));queue
<int> q
;q
.push(0);vis
[flag
][0] = true;while(!q
.empty()){size
= q
.size();while(size
--){cur
= q
.front();dis
[flag
][cur
] = min(dis
[flag
][cur
], step
);q
.pop();if(flag
){for(auto nt
: r
[cur
]){if(vis
[flag
][nt
])continue;vis
[flag
][nt
] = true;q
.push(nt
);}}else{for(auto nt
: b
[cur
]){if(vis
[flag
][nt
])continue;vis
[flag
][nt
] = true;q
.push(nt
);}}}step
++;flag
= !flag
;}}
};
36 ms 13.6 MB
我的CSDN博客地址 https://michael.blog.csdn.net/
長按或掃碼關(guān)注我的公眾號（Michael阿明），一起加油、一起學(xué)習(xí)進步！
總結(jié)
以上是生活随笔為你收集整理的LeetCode 1129. 颜色交替的最短路径（BFS）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
