Frog Position After T Seconds LeetCode solution in Java

1
class Solution {
2
  public double frogPosition(int n, int[][] edges, int t, int target) {
3

4
    List<List<Integer>> graph = new ArrayList<>();
5
    for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
6

7
    for (int i = 0; i < edges.length; i++) {
8

9
      graph.get(edges[i][0]).add(edges[i][1]);
10
      graph.get(edges[i][1]).add(edges[i][0]);
11
    }
12
    boolean[] vis = new boolean[n + 1];
13
    return Sol(graph, 1, t, target, vis);
14
  }
15

16
  public double Sol(List<List<Integer>> graph, int ver, int t, int tar, boolean[] vis) {
17

18
    int count = 0;
19
    for (Integer child : graph.get(ver)) {
20
      if (!vis[child]) count++;
21
    }
22

23
    vis[ver] = true;
24
    if (t < 0) return 0;
25

26
    if (ver == tar) {
27
      if (count == 0 || t == 0) return 1.0;
28
    }
29

30
    if (graph.get(ver).size() == 0) return 0;
31

32
    double ans = 0.0;
33

34
    for (Integer child : graph.get(ver)) {
35

36
      // System.out.println(child);
37
      if (!vis[child]) ans += (double) (1.0 / count) * Sol(graph, child, t - 1, tar, vis);
38
    }
39
    // System.out.println(ans);
40
    vis[ver] = false;
41
    return ans;
42
  }
43
}