|
7 | 7 | importjava.util.Map; |
8 | 8 | importjava.util.Queue; |
9 | 9 |
|
10 | | -/** |
11 | | - * 1377. Frog Position After T Seconds |
12 | | - * |
13 | | - * Given an undirected tree consisting of n vertices numbered from 1 to n. |
14 | | - * A frog starts jumping from the vertex 1. |
15 | | - * In one second, the frog jumps from its current vertex to another unvisited vertex if they are directly connected. |
16 | | - * The frog can not jump back to a visited vertex. |
17 | | - * In case the frog can jump to several vertices it jumps randomly to one of them with the same probability, |
18 | | - * otherwise, when the frog can not jump to any unvisited vertex it jumps forever on the same vertex. |
19 | | - * The edges of the undirected tree are given in the array edges, where edges[i] = [fromi, toi] means that exists an edge connecting directly the vertices fromi and toi. |
20 | | - * Return the probability that after t seconds the frog is on the vertex target. |
21 | | - * |
22 | | - * Example 1: |
23 | | - * Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4 |
24 | | - * Output: 0.16666666666666666 |
25 | | - * Explanation: The figure above shows the given graph. |
26 | | - * The frog starts at vertex 1, jumping with 1/3 probability to the vertex 2 after second 1 and |
27 | | - * then jumping with 1/2 probability to vertex 4 after second 2. |
28 | | - * Thus the probability for the frog is on the vertex 4 after 2 seconds is 1/3 * 1/2 = 1/6 = 0.16666666666666666. |
29 | | - * |
30 | | - * Example 2: |
31 | | - * Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 1, target = 7 |
32 | | - * Output: 0.3333333333333333 |
33 | | - * Explanation: The figure above shows the given graph. The frog starts at vertex 1, jumping with 1/3 = 0.3333333333333333 probability to the vertex 7 after second 1. |
34 | | - * |
35 | | - * Example 3: |
36 | | - * Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 20, target = 6 |
37 | | - * Output: 0.16666666666666666 |
38 | | - * |
39 | | - * Constraints: |
40 | | - * 1 <= n <= 100 |
41 | | - * edges.length == n-1 |
42 | | - * edges[i].length == 2 |
43 | | - * 1 <= edges[i][0], edges[i][1] <= n |
44 | | - * 1 <= t <= 50 |
45 | | - * 1 <= target <= n |
46 | | - * Answers within 10^-5 of the actual value will be accepted as correct. |
47 | | - * */ |
48 | 10 | publicclass_1377 { |
49 | 11 | publicstaticclassSolution1 { |
50 | | -/**credit: https://leetcode.com/problems/frog-position-after-t-seconds/discuss/532505/Java-Straightforward-BFS-Clean-code-O(N)*/ |
| 12 | +/** |
| 13 | + * credit: https://leetcode.com/problems/frog-position-after-t-seconds/discuss/532505/Java-Straightforward-BFS-Clean-code-O(N) |
| 14 | + */ |
51 | 15 | publicdoublefrogPosition(intn,int[][]edges,intt,inttarget) { |
52 | 16 | List<Integer>[]graph =newArrayList[n]; |
53 | 17 | for (inti =0;i <n;i++) { |
|