1377. T 秒后青蛙的位置（Rating 1823）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

1377. T 秒后青蛙的位置

Rating 1823

思路

dfs可以比较简单的找到路径，但是需要注意判断一些边界条件，很容易wa

• 如果路径长度大于t，则不可能到达，返回概率为0
• 如果路径长度小于t
  • 如果目标节点是起始节点 且 t > 0 且 n > 1，则一定会跳走，返回概率0
  • 如果目标节点非起始节点 且 目标节点除了父节点还有其它节点，则一定会跳走，返回概率0
• 如果n == 1，则一直原地跳，返回概率1
• 其余情况正常计算概率即可

代码

class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        g = defaultdict(list)
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)
        
        def dfs(x: int, fa: int, route: list):
            if x == target:
                nonlocal ret
                ret = route.copy()
                return
            for y in g[x]:
                if y == fa:
                    continue
                route.append(y)
                dfs(y, x, route)
                route.pop(-1)

        ret = []
        route = [1]
        dfs(1, -1, route) # dfs找路径
        if len(ret) - 1 > t:
            return 0
        if len(ret) - 1 < t and len(g[target]) > 1:
            return 0
        if n == 1:
            return 1
        if target == 1 and t > 0 and n > 1:
            return 0
        p = 1.0 / len(g[1])
        for i in range(1, len(ret) - 1):
            p *= 1.0 / (len(g[ret[i]]) - 1)
        return p