(B卷,200分)- 跳格子游戏（Java & JS & Python）

题目描述

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

用例

题目解析

本题可以使用拓扑排序求解，关于拓扑排序的解题原理请看

在上面博客中，对拓扑排序做了详细描述，且上面算法题和本题意思几乎一致。

另外，本题输入描述中未给出输入结束条件，因此，我这里判断如果输入是一个空串，则判定为输入结束。

Java算法源码

import java.util.*;

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

    int n = Integer.parseInt(sc.nextLine());

    ArrayList<Integer[]> relations = new ArrayList<>();
    while (sc.hasNextLine()) {
      String line = sc.nextLine();
      if ("".equals(line)) break; // 题目没有说输入终止条件，因此我这里将输入空行作为终止条件
      relations.add(Arrays.stream(line.split(" ")).map(Integer::parseInt).toArray(Integer[]::new));
    }

    System.out.println(getResult(n, relations));
  }

  public static String getResult(int n, ArrayList<Integer[]> relations) {
    int[] inDegree = new int[n];
    HashMap<Integer, ArrayList<Integer>> next = new HashMap<>();

    for (Integer[] relation : relations) {
      int a = relation[0], b = relation[1];
      inDegree[b]++;
      next.putIfAbsent(a, new ArrayList<>());
      next.get(a).add(b);
    }

    LinkedList<Integer> stack = new LinkedList<>();
    for (int i = 0; i < n; i++) {
      if (inDegree[i] == 0) {
        stack.add(i);
      }
    }

    int count = 0;
    while (stack.size() > 0) {
      int a = stack.removeLast();
      count++;

      if (next.containsKey(a)) {
        for (int b : next.get(a)) {
          if (--inDegree[b] == 0) {
            stack.add(b);
          }
        }
      }
    }

    return count == n ? "yes" : "no";
  }
}

JS算法源码

/* 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 relations = lines.map((line) => line.split(" ").map(Number));

    console.log(getResult(n, relations));

    lines.length = 0;
  } else {
    lines.push(line);
  }
});

function getResult(n, relations) {
  const inDegree = new Array(n).fill(0); // 每个顶点的入度
  const next = {}; // 每个顶点的后继

  for (let i = 0; i < relations.length; i++) {
    const [a, b] = relations[i]; // 学完a，才能学b，即 a → b

    inDegree[b]++; // b顶点入度+1
    next[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 ? "yes" : "no";
}

Python算法源码

# 输入获取
n = int(input())

relations = []
while True:
    line = input()

    # 本题没有给输入终止条件，因此我已输入空串为结束条件
    if "" == line:
        break

    relations.append(list(map(int, line.split())))


# 算法入口
def getResult():
    inDegree = [0] * n
    next = {}

    for a, b in relations:
        inDegree[b] += 1
        next.setdefault(a, [])
        next[a].append(b)

    stack = []
    for i in range(n):
        if inDegree[i] == 0:
            stack.append(i)

    count = 0
    while len(stack) > 0:
        a = stack.pop()
        count += 1

        if next.get(a) is not None:
            for b in next[a]:
                inDegree[b] -= 1
                if inDegree[b] == 0:
                    stack.append(b)

    return "yes" if count == n else "no"


# 算法调用
print(getResult())