A
在和 ta
的小伙伴们玩传信息游戏,游戏规则如下:
n
名玩家,所有玩家编号分别为 0 ~ n-1
,其中小朋友 A
的编号为 0
A
可以向 B
传信息,但 B
不能向 A
传信息)。n
,以及按 [玩家编号,对应可传递玩家编号]
关系组成的二维数组 relation
。返回信息从小 A
(编号 0
) 经过 k
轮传递到编号为 n-1
的小伙伴处的方案数;若不能到达,返回 0
。示例 1:
示例 2:
2 <= n <= 10
1 <= k <= 5
1 <= relation.length <= 90, 且 relation[i].length == 2
0 <= relation[i][0],relation[i][1] < n 且 relation[i][0] != relation[i][1]
class Solution {
public int numWays(int n, int[][] relation, int k) {
// 源和目的
int src = 0;
int dest = n - 1;
// 构建有向图的邻接矩阵
List<Integer>[] graph = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
for (int[] edge : relation) {
int u = edge[0];
int v = edge[1];
graph[u].add(v);
}
// 返回结果
return dfs(src, dest, graph, k);
}
// 深度优先搜索,计数传递轮次
private static int dfs(int src, int dest, List<Integer>[] graph, int rounds) {
if (rounds == 0) {
return src == dest ? 1 : 0;
}
int count = 0;
for (int neighbor : graph[src]) {
count += dfs(neighbor, dest, graph, rounds - 1);
}
return count;
}
}
class Solution:
def numWays(self, n: int, relation: List[List[int]], k: int) -> int:
# 源和目的
src = 0
dest = n - 1
# 构建有向图的邻接矩阵
graph = defaultdict(list)
for u, v in relation:
graph[u].append(v)
# 深度优先搜索,计数传递轮次
def dfs(node, rounds):
if rounds == 0:
return 1 if node == dest else 0
count = 0
for neighbor in graph[node]:
count += dfs(neighbor, rounds - 1)
return count
# 返回结果
return dfs(src, k)
class Solution {
public:
int numWays(int n, vector<vector<int>>& relation, int k) {
// 源和目的
int src = 0;
int dest = n - 1;
// 构建有向图的邻接矩阵
vector<vector<int>> graph(n);
for (const auto& edge : relation) {
int u = edge[0];
int v = edge[1];
graph[u].push_back(v);
}
// 返回结果
return dfs(src, dest, graph, k);
}
private:
// 深度优先搜索,计数传递轮次
int dfs(int src, int dest, const vector<vector<int>>& graph, int rounds) {
if (rounds == 0) {
return src == dest ? 1 : 0;
}
int count = 0;
for (int neighbor : graph[src]) {
count += dfs(neighbor, dest, graph, rounds - 1);
}
return count;
}
};
Java语言版
C++语言版