目錄

題目描述

輸入描述

輸出描述

用例

題目解析

算法源碼

---

題目描述

地上共有N個格子，你需要跳完地上所有的格子，但是格子間是有強依賴關系的，跳完前一個格子后，后續的格子才會被開啟，格子間的依賴關系由多組steps數組給出，steps[0]表示前一個格子，steps[1]表示steps[0]可以開啟的格子:

比如[0,1]表示從跳完第0個格子以后第1個格子就開啟了，比如[2,1]，[2,3]表示跳完第2個格子后第1個格子和第3個格子就被開啟了。

請你計算是否能由給出的steps數組跳完所有的格子，如果可以輸出yes，否則輸出no。

說明：

1.你可以從一個格子跳到任意一個開啟的格子

2.沒有前置依賴條件的格子默認就是開啟的

3.如果總數是N，則所有的格子編號為[0,1,2,3…N-1]連續的數組

輸入描述

輸入一個整數N表示總共有多少個格子，接著輸入多組二維數組steps表示所有格子之間的依賴關系。

輸出描述

如果能按照steps給定的依賴順序跳完所有的格子輸出yes，

否則輸出no。

用例

輸入	3 0 1 0 2
輸出	yes
說明	總共有三個格子[0,1,2]，跳完0個格子后第1個格子就開啟了，跳到第0個格子后第2個格子也被開啟了，按照0->1->2或者0->2->1的順序都可以跳完所有的格子

輸入	2 1 0 0 1
輸出	no
說明	總共有2個格子，第1個格子可以開啟第0格子，但是第1個格子又需要第0個格子才能開啟，相互依賴，因此無法完成

輸入	6 0 1 0 2 0 3 0 4 0 5
輸出	yes
說明	總共有6個格子，第0個格子可以開啟第1,2,3,4,5個格子，所以跳完第0個格子之后其他格子都被開啟了，之后按任何順序可以跳完剩余的格子

輸入	5 4 3 0 4 2 1 3 2
輸出	yes
說明	跳完第0個格子可以開啟格子4，跳完格子4可以開啟格子3，跳完格子3可以開啟格子2，跳完格子2可以開啟格子1，按照0->4->3->2->1這樣就跳完所有的格子

輸入	4 1 2 1 0
輸出	yes
說明	總共4個格子[0,1,2,3]，格子1和格子3沒有前置條件所以默認開啟，格子1可以開啟格子0和格子2，所以跳到格子1之后就可以開啟所有的格子，因此可以跳完所有格子。

題目解析

本題可以使用拓撲排序求解，關于拓撲排序的解題原理請看LeetCode - 207 課程表_伏城之外的博客-CSDN博客

在上面博客中，對拓撲排序做了詳細描述，且上面算法題和本題意思幾乎一致。

另外，本題輸入描述中未給出輸入結束條件，因此，我這里判斷如果輸入是一個空串，則判定為輸入結束。

算法源碼

/* JavaScript Node ACM模式 控制臺輸入獲取 */ const readline = require("readline");const rl = readline.createInterface({input: process.stdin,output: process.stdout, });const lines = []; rl.on("line", (line) => {if (line === "") {const n = parseInt(lines.shift());const prerequisites = lines.map((line) => line.split(" ").map(Number));console.log(canFinish(n, prerequisites) ? "yes" : "no");lines.length = 0;} else {lines.push(line);} });function canFinish(n, prerequisites) {const inDegree = new Array(n).fill(0); // 每個頂點的入度const next = {}; // 每個頂點的后繼for (let i = 0; i < prerequisites.length; i++) {const [a, b] = prerequisites[i]; // 學完a，才能學b，即 a → binDegree[b]++; // b頂點入度+1next[a] ? next[a].push(b) : (next[a] = [b]); // a頂點的后繼加入b}const stack = [];for (let i = 0; i < n; i++) {if (inDegree[i] === 0) {stack.push(i);}}let count = 0;while (stack.length) {const a = stack.pop();count++;next[a]?.forEach((b) => {if (--inDegree[b] === 0) stack.push(b);});}return count === n; }

總結

以上是生活随笔為你收集整理的华为机试 - 跳格子游戏的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。