Frog Position After T Seconds

Problem Id: 1377 Difficulty: Hard Tag: Depth-first Search


Intuition

The opportunity could be easily calculated by DFS.

In additional to the general DFS, we need to first pay attention to the time we left. If it is less than 0, we should stop the DFS process.

Then, we need to pass the current opportunity as an additional variable to the DFS function. So we could use it as the return value when we find the target.

Solution


class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        # Build up the tree
        target -= 1
        adj = [[] for _ in range(n)]
        for i, j in edges:
            adj[i - 1].append(j - 1)
            adj[j - 1].append(i - 1)

        # Do a DFS to get the opportunities
        return self._dfs(0, -1, adj, t, target, 1.)

    def _dfs(self, node, parent, adj, timeLeft, target, opportunity):
        if parent == -1:
            tmp = len(adj[node])
        else:
            tmp = len(adj[node]) - 1

        if node is target:
            if timeLeft == 0 or tmp == 0:
                return opportunity
            return 0
        elif timeLeft == 0:
            return 0.

        if tmp == 0:
            return 0.
        opportunity = opportunity / tmp
        for child in adj[node]:
            if child != parent:
                tmp = self._dfs(child, node, adj, timeLeft - 1, target, opportunity)
                if tmp > 0:
                    return tmp
        return 0.