【华为OD-E卷 -51 跳格子游戏 100分（python、java、c++、js、c）】

id="article_content" class="article_content clearfix" style="height: 2000px; overflow: hidden;"> id="content_views" class="markdown_views prism-tomorrow-night">

【华为OD-E卷 - 跳格子游戏 100分（python、java、c++、js、c）】

题目

地上共有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。

备注

  • 1 ≤ N ＜ 500 step[i].length = 2 0 ≤ step[i][0]，step[i][1] ＜ N

用例

用例一：
输入：
3
0 1
0 2
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
  • 1
  • 2
  • 3
输出：
yes
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
  • 1
用例二：
输入：
2
1 0
0 1
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
  • 1
  • 2
  • 3
输出：
no
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
用例三：
输入：
6
0 1
0 2
0 3
0 4
0 5
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
输出：
yes
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
用例四：
输入：
5
4 3
0 4
2 1
3 2
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
输出：
yes
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

python解法

以下是解题的主要步骤：

构建图与入度表：

使用 defaultdict 构建邻接表表示有向图。
使用一个列表 in_degree 来记录每个节点的入度（指向该节点的边数）。
初始化队列：

将入度为 0 的节点（没有依赖的节点）加入队列，因为这些节点可以作为起始点开始遍历。
拓扑排序：

使用队列按拓扑顺序遍历图。
每遍历一个节点，将其邻居节点的入度减 1，如果某个邻居节点的入度变为 0，则将其加入队列。
检查结果：

如果拓扑排序访问的节点数等于图中节点总数 N，则说明可以完成所有格子的跳跃。
如果访问的节点数小于 N，则说明存在环，无法完成跳跃

from collections import deque, defaultdict

def can_finish_all_grids(N, steps):
    """
    判断是否可以跳完所有格子。
    
    :param N: 总格子数（节点数）
    :param steps: 每个格子之间的跳跃关系（有向边列表）
    :return: "yes" 如果可以跳完所有格子，否则 "no"
    """
    # 构建图（邻接表）和入度数组
    graph = defaultdict(list)  # 存储邻接关系
    in_degree = [0] * N  # 记录每个节点的入度

    # 遍历跳跃关系，填充图和入度
    for step in steps:
        u, v = step  # u -> v 表示从 u 跳到 v
        graph[u].append(v)  # 添加邻接关系
        in_degree[v] += 1  # 更新 v 的入度

    # 初始化队列，将所有入度为 0 的节点加入队列
    queue = deque()
    for i in range(N):
        if in_degree[i] == 0:
            queue.append(i)

    visited_count = 0  # 记录访问过的节点数

    # 拓扑排序
    while queue:
        node = queue.popleft()  # 从队列中取出一个节点
        visited_count += 1  # 标记节点为已访问

        # 遍历当前节点的所有邻居
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1  # 邻居节点的入度减 1
            if in_degree[neighbor] == 0:  # 如果邻居节点入度变为 0，则加入队列
                queue.append(neighbor)

    # 如果访问的节点数等于总节点数 N，则可以跳完所有格子
    return "yes" if visited_count == N else "no"

# 读取输入
import sys
input = sys.stdin.read
data = input().split()

# 解析输入数据
N = int(data[0])  # 第一个数字是格子总数
steps = []  # 后续每两个数字构成一对跳跃关系
for i in range(1, len(data), 2):
    steps.append([int(data[i]), int(data[i + 1])])

# 计算并输出结果
result = can_finish_all_grids(N, steps)
print(result)

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

java解法

以下是解题步骤和逻辑：

构建图和入度数组：

使用一个邻接表（List graph）表示有向图的边。
使用数组 inDegree 记录每个节点的入度（被指向的次数）。
初始化队列：

将所有入度为 0 的节点（没有依赖的起始点）加入队列，作为拓扑排序的起点。
拓扑排序：

使用队列按拓扑顺序遍历图。
每遍历一个节点，将其邻居节点的入度减 1，如果某个邻居节点的入度变为 0，则将其加入队列。
检查结果：

如果拓扑排序访问的节点数等于图中总节点数 n，则说明图中不存在环，所有格子可以跳完。
如果访问的节点数小于 n，则说明存在环，无法完成跳跃

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读取节点总数 n
        int n = Integer.parseInt(sc.nextLine());

        // 初始化入度数组和邻接表
        int[] inDegree = new int[n]; // 记录每个节点的入度
        List<List<Integer>> graph = new ArrayList<>(); // 邻接表表示有向图

        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>()); // 初始化每个节点的邻接表
        }

        // 构建图
        while (sc.hasNextLine()) {
            String line = sc.nextLine(); // 读取输入行
            if (line.isEmpty()) break; // 如果是空行，停止读取
            String[] parts = line.split(" "); // 分割起点和终点
            int from = Integer.parseInt(parts[0]); // 起点
            int to = Integer.parseInt(parts[1]); // 终点
            graph.get(from).add(to); // 添加边 from -> to
            inDegree[to]++; // 更新终点节点的入度
        }

        // 初始化队列，加入所有入度为 0 的节点
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) { // 如果某节点的入度为 0，加入队列
                queue.add(i);
            }
        }

        // 拓扑排序
        int count = 0; // 记录访问过的节点数
        while (!queue.isEmpty()) {
            int current = queue.poll(); // 从队列中取出一个节点
            count++; // 标记当前节点为已访问
            for (int neighbor : graph.get(current)) { // 遍历当前节点的所有邻居
                inDegree[neighbor]--; // 邻居节点的入度减 1
                if (inDegree[neighbor] == 0) { // 如果邻居节点的入度变为 0，加入队列
                    queue.add(neighbor);
                }
            }
        }

        // 判断是否可以访问所有节点
        System.out.println(count == n ? "yes" : "no"); // 如果访问节点数等于 n，输出 "yes"，否则输出 "no"
    }
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

C++解法

更新中
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

C解法

更新中
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

JS解法

更新中
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏

注：本文转载自blog.csdn.net的CodeClimb的文章"https://blog.csdn.net/CodeClimb/article/details/144947608"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！