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

25-03-07 19:41

2305

7793

blog.csdn.net

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"}">

1

用例三：

输入：

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"}">

1
2
3
4
5
6

输出：

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

1

用例四：

输入：

5
4 3
0 4
2 1
3 2
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5

输出：

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

python解法

解题思路：
问题描述

有 N 个格子，从 0 到 N-1 编号，某些格子之间存在方向性跳跃规则（例如，从格子 u 可以跳到格子 v）。
给定所有跳跃规则，判断是否可以遍历完所有的格子。
问题本质是判断图是否为一个有向无环图（DAG），并且是否可以通过拓扑排序遍历所有节点。
解决方案

使用拓扑排序检测是否可以遍历所有节点：
构建图：用邻接表表示跳跃规则。
统计每个节点的入度（被指向的次数）。
将入度为 0 的节点加入队列，表示这些节点可以作为起始点。
依次从队列中取出节点，减少其邻居节点的入度。如果邻居节点的入度减为 0，将其加入队列。
如果最终遍历的节点数等于总格子数 N，则说明可以遍历完所有格子。
算法流程

初始化邻接表 graph 和入度数组 in_degree。
遍历所有跳跃规则，构建图并更新入度。
初始化队列，将入度为 0 的节点加入队列。
使用队列进行拓扑排序，逐步减少节点的入度。
检查是否访问了所有节点：
如果访问的节点数等于 N，返回 “yes”；
否则，返回 “no”

from collections import deque, defaultdict

def can_finish_all_grids(N, steps):
    """
    判断是否可以跳完所有格子
    :param N: 格子数量
    :param steps: 跳跃规则，格式为 [[u1, v1], [u2, v2], ...]
    :return: "yes" 或 "no"
    """
    # 构建图的邻接表和入度数组
    graph = defaultdict(list)  # 邻接表表示跳跃规则
    in_degree = [0] * N        # 入度数组

    # 遍历跳跃规则，构建图并统计入度
    for step in steps:
        u, v = step
        graph[u].append(v)     # 从 u 到 v 的跳跃
        in_degree[v] += 1      # 增加 v 的入度

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

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

    # 使用队列进行拓扑排序
    while queue:
        node = queue.popleft()  # 取出队首节点
        visited_count += 1      # 计数已访问的节点数
        for neighbor in graph[node]:  # 遍历当前节点的邻居
            in_degree[neighbor] -= 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"}">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

java解法

解题思路
问题描述

给定一个有 n 个节点的有向图，每条边表示从一个节点可以跳到另一个节点。
需要判断是否可以访问图中的所有节点，即判断图是否是一个有向无环图（DAG），并且是否所有节点都可以通过拓扑排序访问。
解决方案

使用拓扑排序方法判断是否可以访问所有节点：
构建图：使用邻接表表示有向图，并记录每个节点的入度。
入度为 0 的节点入队：初始将所有入度为 0 的节点加入队列。
广度优先遍历：从队列中逐个取出节点，访问其邻居并减少邻居的入度。当某邻居的入度减为 0 时，将其加入队列。
统计访问的节点数：如果访问的节点数等于图的节点总数 n，说明可以访问所有节点，否则不能。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 读取节点数量
        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); // 添加边到邻接表
            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");
    }
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

C++解法

解题思路

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

C解法

解题思路
问题描述

有一个包含 N 个节点的有向图，每个节点从 0 到 N-1 编号。
给定图的有向边 (u, v)，表示从节点 u 可以跳到节点 v。
需要判断是否可以从图的某些起点开始访问图中的所有节点。
解决方案

使用拓扑排序（Kahn 算法）来判断图是否为有向无环图（DAG），并检查是否可以访问所有节点：
构建图和统计入度：
使用邻接表表示图，记录每个节点的出边。
使用数组记录每个节点的入度（指向它的边的数量）。
初始化队列：
将所有入度为 0 的节点加入队列，这些节点可以作为起点。
拓扑排序：
依次从队列中取出节点，访问其邻居并减少邻居节点的入度。
如果某邻居节点的入度减少到 0，将其加入队列。
判断结果：
如果最终访问的节点数等于图中的节点总数，则可以访问所有节点，返回 “yes”。
否则，返回 “no”

#include 
#include 
#include 

// 邻接表结构
typedef struct {
    int* data;  // 存储邻居节点的数组
    int size;   // 当前邻接节点的数量
    int cap;    // 邻接节点数组的容量
} AdjList;

// 队列结构
typedef struct {
    int* data;  // 存储队列中元素的数组
    int front;  // 队列头部索引
    int rear;   // 队列尾部索引
    int cap;    // 队列的容量
} Queue;

// 创建队列
Queue* create_queue(int cap) {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->data = (int*)malloc(sizeof(int) * cap);
    q->front = q->rear = 0;
    q->cap = cap;
    return q;
}

// 入队操作
void enqueue(Queue* q, int x) {
    if (q->rear == q->cap) {
        q->cap *= 2;  // 动态扩容
        q->data = (int*)realloc(q->data, sizeof(int) * q->cap);
    }
    q->data[q->rear++] = x;
}

// 出队操作
int dequeue(Queue* q) {
    if (q->front == q->rear)  // 队列为空
        return -1;
    return q->data[q->front++];
}

// 判断队列是否为空
int is_empty(Queue* q) {
    return q->front == q->rear;
}

// 主函数
int main() {
    int N;
    scanf("%d", &N);  // 读取节点数量

    // 初始化邻接表
    AdjList* graph = (AdjList*)malloc(sizeof(AdjList) * N);
    for (int i = 0; i < N; i++) {
        graph[i].data = NULL;   // 初始无邻居节点
        graph[i].size = 0;      // 邻居节点数量为 0
        graph[i].cap = 0;       // 邻接表容量为 0
    }

    // 初始化入度数组
    int* in_degree = (int*)calloc(N, sizeof(int));

    int u, v;

    // 读取有向边
    while (scanf("%d %d", &u, &v) != EOF) {
        // 动态扩容邻接表
        if (graph[u].size == graph[u].cap) {
            graph[u].cap = graph[u].cap == 0 ? 2 : graph[u].cap * 2;
            graph[u].data = (int*)realloc(graph[u].data, sizeof(int) * graph[u].cap);
        }
        graph[u].data[graph[u].size++] = v;  // 将 v 加入 u 的邻接表
        in_degree[v]++;  // 增加节点 v 的入度
    }

    // 创建队列并将入度为 0 的节点加入队列
    Queue* queue = create_queue(N);
    for (int i = 0; i < N; i++) {
        if (in_degree[i] == 0) {  // 入度为 0 的节点
            enqueue(queue, i);
        }
    }

    int visited_count = 0;  // 记录访问的节点数

    // 拓扑排序
    while (!is_empty(queue)) {
        int node = dequeue(queue);  // 取出队列头部节点
        visited_count++;  // 计数已访问的节点数

        // 遍历当前节点的邻居
        for (int i = 0; i < graph[node].size; i++) {
            int neighbor = graph[node].data[i];
            in_degree[neighbor]--;  // 减少邻居节点的入度
            if (in_degree[neighbor] == 0) {  // 入度为 0 的节点加入队列
                enqueue(queue, neighbor);
            }
        }
    }

    // 判断是否访问了所有节点
    printf("%s\n", visited_count == N ? "yes" : "no");

    // 释放动态分配的内存
    for (int i = 0; i < N; i++) {
        free(graph[i].data);  // 释放每个节点的邻接表
    }
    free(graph);              // 释放邻接表数组
    free(in_degree);          // 释放入度数组
    free(queue->data);        // 释放队列数据
    free(queue);              // 释放队列结构

    return 0;
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

JS解法

解题思路

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

注意：

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

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

复制链接

发表评论

注册

评论记录：

未查询到任何数据！