from collections import defaultdict, deque
class Solution:
def frogPosition(self, n, edges, t, target):
# Build the tree as an adjacency list
tree = defaultdict(list)
for u, v in edges:
tree[u].append(v)
tree[v].append(u)
# BFS queue: (current_node, parent, prob, time)
queue = deque()
queue.append((1, 0, 1.0, 0))
while queue:
node, parent, prob, time = queue.popleft()
if time == t:
if node == target:
return prob
continue
# Children except parent
children = [child for child in tree[node] if child != parent]
if not children:
# Leaf node: frog stays
if node == target:
if time <= t:
return prob
continue
if node == target:
if time < t:
return 0.0
for child in children:
queue.append((child, node, prob / len(children), time + 1))
return 0.0
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
vector<vector<int>> tree(n + 1);
for (auto& e : edges) {
tree[e[0]].push_back(e[1]);
tree[e[1]].push_back(e[0]);
}
queue<tuple<int, int, double, int>> q;
q.push({1, 0, 1.0, 0});
while (!q.empty()) {
auto [node, parent, prob, time] = q.front(); q.pop();
if (time == t) {
if (node == target) return prob;
continue;
}
vector<int> children;
for (int child : tree[node]) {
if (child != parent) children.push_back(child);
}
if (children.empty()) {
if (node == target && time <= t) return prob;
continue;
}
if (node == target) {
if (time < t) return 0.0;
}
for (int child : children) {
q.push({child, node, prob / children.size(), time + 1});
}
}
return 0.0;
}
};
import java.util.*;
class Solution {
public double frogPosition(int n, int[][] edges, int t, int target) {
List<List<Integer>> tree = new ArrayList<>();
for (int i = 0; i <= n; i++) tree.add(new ArrayList<>());
for (int[] e : edges) {
tree.get(e[0]).add(e[1]);
tree.get(e[1]).add(e[0]);
}
Queue<int[]> q = new LinkedList<>();
Queue<Double> pq = new LinkedList<>();
q.offer(new int[]{1, 0, 0});
pq.offer(1.0);
while (!q.isEmpty()) {
int[] curr = q.poll();
double prob = pq.poll();
int node = curr[0], parent = curr[1], time = curr[2];
if (time == t) {
if (node == target) return prob;
continue;
}
List<Integer> children = new ArrayList<>();
for (int child : tree.get(node)) {
if (child != parent) children.add(child);
}
if (children.size() == 0) {
if (node == target && time <= t) return prob;
continue;
}
if (node == target) {
if (time < t) return 0.0;
}
for (int child : children) {
q.offer(new int[]{child, node, time + 1});
pq.offer(prob / children.size());
}
}
return 0.0;
}
}
/**
* @param {number} n
* @param {number[][]} edges
* @param {number} t
* @param {number} target
* @return {number}
*/
var frogPosition = function(n, edges, t, target) {
const tree = Array.from({length: n+1}, () => []);
for (const [u, v] of edges) {
tree[u].push(v);
tree[v].push(u);
}
const queue = [];
queue.push([1, 0, 1.0, 0]);
while (queue.length > 0) {
const [node, parent, prob, time] = queue.shift();
if (time === t) {
if (node === target) return prob;
continue;
}
const children = tree[node].filter(child => child !== parent);
if (children.length === 0) {
if (node === target && time <= t) return prob;
continue;
}
if (node === target) {
if (time < t) return 0.0;
}
for (const child of children) {
queue.push([child, node, prob / children.length, time + 1]);
}
}
return 0.0;
};
You are given a tree with n nodes, labeled from 1 to n. The tree is represented by an array of edges, where each edge connects two nodes. A frog starts at node 1 at time 0. Every second, the frog jumps to an unvisited child node with equal probability. If there are no unvisited children (i.e., the frog is at a leaf), it stays at its current node.
Given an integer t (the number of seconds) and a target node, return the probability that the frog is on target after t seconds.
The problem asks for the probability that the frog is at a specific node after t seconds.
Since the frog can only move to unvisited children, and each move is random, we need to track all possible paths the frog could take and their probabilities.
A brute-force approach would be to enumerate all possible paths of length up to t, but this quickly becomes infeasible for large trees due to exponential growth.
Instead, we can use Breadth-First Search (BFS) or Depth-First Search (DFS) to simulate the frog's movement, keeping track of the probability at each step.
At each node, the probability of reaching any child is the current probability divided by the number of unvisited children. If the frog reaches a leaf, it stays there, and the probability doesn't change for the remaining time steps.
1.target node exactly at time t, return the probability.target before time t but cannot move further (i.e., it's a leaf), it can stay there until time t.target at time t, return 0.0.This approach ensures that we only consider valid paths and efficiently compute the required probability.
Sample Input:
n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4
Output: 0.16666666666666666 (i.e., 1/6)
The optimized approach is efficient and scales well with large trees.
To solve the "Frog Position After T Seconds" problem, we simulate the frog's movement through the tree using BFS or DFS, updating the probability at each step. By carefully handling the rules for leaf nodes and tracking the probability for each path, we efficiently compute the chance that the frog is at the target node after t seconds. The solution is both elegant and efficient, leveraging tree traversal and probability propagation.