1377. Frog Position After T Seconds¶
题目信息¶
- 题号:
1377
- 难度:
Hard
- 主题:
树、概率、深度优先搜索
- 原题:
- 重点:
青蛙从节点
1开始,每秒等概率跳到尚未访问的相邻节点;没有未访问邻居时留在原地
题目重述¶
给定一棵包含 n 个节点的无向树。青蛙初始位于节点 1。每秒钟,若当前位置存在未访问过的相邻节点,它会从这些节点中等概率选择一个跳过去;若不存在,则继续停留在当前位置。
请返回恰好 t 秒后青蛙位于 target 节点的概率。已经访问过的节点不能再次跳入。
1 <= n <= 100,0 <= t <= 50,树边数为 n-1。
自建示例¶
根的两个孩子被等概率选择:
输入:n = 3, edges = [[1,2],[1,3]], t = 1, target = 2
输出:0.5
解释:第一秒从两个未访问邻居中等概率选择。
到达叶节点后会继续停留:
输入:同一棵树,t = 2, target = 2
输出:0.5
解释:第一秒到达节点 2 的概率为二分之一,之后没有未访问邻居,因此留在节点 2。