LCP07.传递信息

链接：LCP07.传递信息
难度：Easy
标签：深度优先搜索、广度优先搜索、图、动态规划
简介：给定总玩家数 n，以及按 [玩家编号,对应可传递玩家编号] 关系组成的二维数组 relation。返回信息从小 A (编号 0 ) 经过 k 轮传递到编号为 n-1 的小伙伴处的方案数；若不能到达，返回 0。

题解 1 - typescript

• 编辑时间：2021-07-01
• 执行用时：104ms
• 内存消耗：41.5MB
• 编程语言：typescript
• 解法介绍：储存每个伙伴的下一个伙伴。

function numWays(n: number, relation: number[][], k: number): number {
  const nextPartnerMap = new Map<number, Set<number>>();
  for (const [cur, next] of relation) {
    let set = nextPartnerMap.get(cur);
    if (!set) nextPartnerMap.set(cur, (set = new Set()));
    set.add(next);
  }
  let list = [0];
  while (k--) {
    list = list
      .map(item => (nextPartnerMap.has(item) ? [...nextPartnerMap.get(item)!] : []))
      .flat();
  }
  return list.filter(v => v === n - 1).length;
}