LCP 07. 传递信息

水深无声 2023-10-04 16:28 59阅读 0赞

小朋友 A 在和 ta 的小伙伴们玩传信息游戏，游戏规则如下：

有 n 名玩家，所有玩家编号分别为 0 ～ n-1，其中小朋友 A 的编号为 0  
每个玩家都有固定的若干个可传信息的其他玩家（也可能没有）。传信息的关系是单向的（比如 A 可以向 B 传信息，但 B 不能向 A 传信息）。  
每轮信息必须需要传递给另一个人，且信息可重复经过同一个人  
给定总玩家数 n，以及按 \[玩家编号,对应可传递玩家编号\] 关系组成的二维数组 relation。返回信息从小 A (编号 0 ) 经过 k 轮传递到编号为 n-1 的小伙伴处的方案数；若不能到达，返回 0。

解法一：BFS

// 解法一  BFS
    class Solution {
        
    
        public static int res = 0;
        public int numWays(int n, int[][] relation, int k) {
        
    
           
            // 进行归类
            HashMap<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();
            for (int i = 0; i < relation.length; i++) {
        
                int a = relation[i][0];
                Set<Integer> s = map.getOrDefault(a, new HashSet<Integer>());
                s.add(relation[i][1]);
                map.put(a, s);
            }
            // 进行BFS
            // 定义一个队列
            Deque<Integer> deq = new ArrayDeque<Integer>();
            deq.addLast(0);
            while (!deq.isEmpty() && k-- > 0) {
        
                // 队列不为空则弹出,获取其指向的元素集合
                // 需要一个一个处理，所以用while遍历
                int size = deq.size();
                while (size-- > 0) {
        
                    int cur = deq.pollFirst();
                    Set<Integer> s = map.get(cur);
                    if (s == null) continue;
                    // 将后续集合入队
                    for (int i : s) {
        
                        deq.addLast(i);
                    }
                }
                
    
            }
            // 最后判断集合中的元素有哪些达到了n - 1
            
            while (!deq.isEmpty()) {
        
                int cur = deq.pollFirst();
                if (cur == n - 1) res++;
            }
    
            return res;
        }
    
        
    }

解法二：DFS

//解法二  DFS
    class Solution {
        
    
        //public static int res = 0;
        HashMap<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();
        int n, k, ans;
        public int numWays(int _n, int[][] relation, int _k) {
        
    
           n = _n; k = _k;
            // 进行归类
            
            for (int[] r : relation) {
        
                int a = r[0]; 
                int b = r[1];
                Set<Integer> s = map.getOrDefault(a, new HashSet<>());
                s.add(b);
                map.put(a, s);
            }
            dfs(0, 0);
            return ans;
        }
        // 定义深度搜索函数
        public void dfs(int u, int i) {
        
            // 如果数目达到k，则判断并返回
            if (i == k) {
        
                if (u == n - 1) ans++;
                return;
            }
            Set<Integer> s = map.get(u);
            if (s == null) return;
            for (int cur : s) {
        
                dfs(cur, i + 1);
            }
    
        }
    
        
    }

解法三：动态规划

class Solution {
        
    
        //public static int res = 0;
        HashMap<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();
        // int n, k, ans;
        public int numWays(int n, int[][] relation, int k) {
        
            
            int[][] f = new int[k + 1][n];
            f[0][0] = 1;
    
            for (int i = 1; i <= k; i++) {
        
                for (int[] cur : relation) {
        
                    int a = cur[0], b = cur[1];
                    f[i][b] += f[i - 1][a];
                }
            }
            return f[k][n - 1];
    
        }
    
        
    }