Frog Position After T Seconds LeetCode solution in C++

1
class Solution {
2
 public:
3
  double frogPosition(int n, vector<vector<int>> &edges, int t, int target) {
4
    unordered_map<int, vector<int>> adjList;
5
    for (const auto &edge : edges) {
6
      adjList[edge[0]].push_back(edge[1]);
7
      adjList[edge[1]].push_back(edge[0]);
8
    }
9

10
    // BFS way
11
    queue<pair<int, double>> Q;
12
    Q.push({1, 1.0});
13
    int time = 0;
14
    vector<int> visited(n + 1, false);
15

16
    while (not Q.empty()) {
17
      int size = Q.size();
18

19
      if (time > t) break;
20

21
      while (size--) {
22
        auto pp = Q.front();
23
        Q.pop();
24
        int node = pp.first;
25
        double prob = pp.second;
26

27
        visited[node] = true;
28

29
        // Count the unvisited nbr
30
        int nbrCount = 0;
31
        for (auto &nbr : adjList[node]) {
32
          if (not visited[nbr]) nbrCount++;
33
        }
34

35
        if (node == target) {
36
          if (time == t) return prob;
37
          if (time < t) {
38
            // Check if any unvisited ? if yes, then frog would jump there and
39
            // not be able to jump back here
40
            if (nbrCount > 0) return 0.0;
41

42
            // else return the same prob
43
            return prob;
44
          }
45
        }
46

47
        for (auto &nbr : adjList[node]) {
48
          if (not visited[nbr]) {
49
            // update the prob as it will be divided by number of nbr
50
            Q.push({nbr, (prob * (1.0 / nbrCount))});
51
          }
52
        }
53
      }
54

55
      time++;
56
    }
57

58
    return 0.0;
59
  }
60
};