1377. T 秒后青蛙的位置 DFS

1377. T 秒后青蛙的位置

难度困难44

给你一棵由 n 个顶点组成的无向树，顶点编号从 1 到 n。青蛙从 顶点 1 开始起跳。规则如下：

• 在一秒内，青蛙从它所在的当前顶点跳到另一个 未访问 过的顶点（如果它们直接相连）。
• 青蛙无法跳回已经访问过的顶点。
• 如果青蛙可以跳到多个不同顶点，那么它跳到其中任意一个顶点上的机率都相同。
• 如果青蛙不能跳到任何未访问过的顶点上，那么它每次跳跃都会停留在原地。

无向树的边用数组 edges 描述，其中 edges[i] = [fromi, toi] 意味着存在一条直接连通 fromi 和 toi 两个顶点的边。

返回青蛙在 t 秒后位于目标顶点 target 上的概率。

示例 1：

输入：n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4
输出：0.16666666666666666 
解释：上图显示了青蛙的跳跃路径。青蛙从顶点 1 起跳，第 1 秒 有 1/3 的概率跳到顶点 2 ，然后第 2 秒 有 1/2 的概率跳到顶点 4，因此青蛙在 2 秒后位于顶点 4 的概率是 1/3 * 1/2 = 1/6 = 0.16666666666666666 。 

示例 2：

输入：n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 1, target = 7
输出：0.3333333333333333
解释：上图显示了青蛙的跳跃路径。青蛙从顶点 1 起跳，有 1/3 = 0.3333333333333333 的概率能够 1 秒 后跳到顶点 7 。 

提示：

• 1 <= n <= 100
• edges.length == n - 1
• edges[i].length == 2
• 1 <= ai, bi <= n
• 1 <= t <= 50
• 1 <= target <= n

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/frog-position-after-t-seconds
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

做题结果

成功，意外的简单

方法：DFS

1. 建立图

2. DFS查询，特别地，分支查到目标的情况才进行处理，否则返回-1
3. 特判：
   • 时间不足到达目标点，返回-1
   • 到达目标点，但是时间没结束，也不是叶子节点，因为还能继续跳动无法停留，返回-1
   • 没有子节点返回-1
4. 因为是树，只要不返回父节点，就不会走回头路，因此，不用处理访问节点，直接记录当前位置父节点即可，初始父节点-1
5. 答案求的是概率，-1情况返回0，其他情况返回 1/ans

class Solution {
    public double frogPosition(int n, int[][] edges, int t, int target) {
        Set[] graph = new HashSet[n+1];
        Arrays.setAll(graph,o->new HashSet<>());
        for(int[] edge:edges){
            int u = edge[0];
            int v = edge[1];
            graph[u].add(v);
            graph[v].add(u);
        }
        long ans = dfs(graph,1,-1,t,target);
        return ans == -1?0:1.0/ans;
    }
 
    private long dfs(Set[] graph, int curr, int parent, int time, int target){
 
        long childSize = graph[curr].size()-(parent==-1?0:1);
        if(curr == target){
            if(time == 0||!hasNext(graph,curr,parent)) return 1;
            return -1;
        }
        if(!hasNext(graph,curr,parent)) return -1;
        if(time == 0 || childSize==0) return -1;
        for(Integer next:graph[curr]){
            if(next==parent) continue;
            long sub = dfs(graph,next,curr,time-1,target);
            if(sub!=-1) return sub*childSize;
        }
        return -1;
    }
 
    private boolean hasNext(Set[] graph, int curr, int parent){
        return graph[curr].size()>1||( graph[curr].size()==1 && !graph[curr].contains(parent));
    }
}