LeetCode 5355. T 秒后青蛙的位置
传送门：https://leetcode-cn.com/problems/frog-position-after-t-seconds/解：
建图+BFS（DFS也可）
t其实是对层数的限制，用BFS比较好理解。
注意青蛙在目的地停留的条件：
1.所在层数（顶点层数按0算）等于t
或
2.所在层数小于t，但目的地为叶节点
class Solution {
public:
vector<int> adj;
double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
for (auto edge: edges) adj, edge)].push_back(max(edge, edge));
queue<pair<int, double>> q;
q.push({1, 1.0});
while (int k = q.size())
{
while (k--)
{
auto now = q.front();
q.pop();
int num = adj.size();
if (target == now.first) return (!t || (t > 0 && !num)) ? now.second : 0.0;
for (int each: adj) q.push({each, now.second / num});
}
--t;
}
return 0.0;
}
};
页:
[1]