Leetcode Problem 1377. Frog Position After T Seconds

1377. Frog Position After T Seconds

Leetcode Solutions

DFS with Probability Propagation

  1. Create an adjacency list to represent the tree.
  2. Initialize a visited set to keep track of visited vertices.
  3. Define a recursive DFS function that takes the current vertex, the time elapsed, and the accumulated probability.
  4. In the DFS function, mark the current vertex as visited.
  5. If the current vertex is the target and the time is equal to t or there are no more unvisited neighbors, return the accumulated probability.
  6. Calculate the number of unvisited neighbors and divide the current probability by this number to get the probability of moving to any one neighbor.
  7. Recursively call DFS for each unvisited neighbor with the updated time and probability.
  8. If the target is not reached within t seconds, return 0.
  9. Call the DFS function from the starting vertex with time 0 and probability 1.
  10. Return the result of the DFS call.
UML Thumbnail

BFS with Probability Propagation

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...