共计 1484 个字符，预计需要花费 4 分钟才能阅读完成。
1377. T 秒后青蛙的地位
关键词：深度优先
题目起源：1377. T 秒后青蛙的地位 – 力扣（Leetcode）
题目形容
T 深度优先 给你一棵由 n 个顶点组成的无向树，顶点编号从 1 到 n。青蛙从 顶点 1 开始起跳。规定如下：
- 在一秒内，青蛙从它所在的以后顶点跳到另一个 未拜访 过的顶点（如果它们间接相连）。
- 青蛙无奈跳回曾经拜访过的顶点。
- 如果青蛙能够跳到多个不同顶点，那么它跳到其中任意一个顶点上的机率都雷同。
- 如果青蛙不能跳到任何未拜访过的顶点上，那么它每次跳跃都会停留在原地。
无向树的边用数组 edges 形容，其中 edges[i] = [fromi, toi] 意味着存在一条间接连通 fromi 和 toi 两个顶点的边。
返回青蛙在 t 秒后位于指标顶点 target 上的概率。
输出：n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4
输入：0.16666666666666666 输出：n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 1, target = 7
输入：0.3333333333333333 数据范畴
1 <= n <= 100
edges.length == n - 1
edges[i].length == 2
1 <= ai, bi <= n
1 <= t <= 50
1 <= target <= n问题剖析
无向树的终点为 1，且青蛙不能往回跳，故题目所说的无向树实际上是一棵有向树。
依题意，当工夫为 t 时，若青蛙能位于 target，则概率不为 0，否则概率为 0。故存在以下两种状况概率不为 0：
- 工夫为 t，且青蛙恰好位于 target
- 工夫小于 t，但 t 为叶子结点，故可原地跳，则工夫为 t 时，青蛙可位于 target
于是，题目等价于判断是否存在以上两种状况。
每跳一次，破费工夫为 1，故 t 可看做深度限度，根节点 1 的深度为 0。
因为要计算概率，每个结点只能跳到其子结点，故须要统计每个点的子结点的数量。
对于此类无关树的搜寻问题，显然能够采纳深搜来求解。采纳深搜时，可做如下优化
- 当搜寻到结点 target 时，后果是能够确定的
- 当深度大于 t 时，不用持续往下搜寻，可间接返回。
代码实现
double frogPosition(int n, vector<vector<int>> &edges, int t, int target) {memset(h, -1, sizeof h);
memset(cnt, -1, sizeof cnt);
// 预处理
for (const auto &v: edges) {add(v[0], v[1]), add(v[1], v[0]);
cnt[v[0]]++, cnt[v[1]]++;
}
cnt[1]++;
// 深搜
int res = 0;
function<int(int, int, int, int)> dfs = [&](int u, int p, int d, int pro) {
// 找到指标顶点：后果确定
if (u == target) {
res = pro;
// 工夫刚好或没到工夫但可原地踏步则阐明存在概率
return (d == t || d < t && !cnt[u]) ? 1 : -1;
}
// 未找到指标顶点但工夫已过：后果未定
if (d >= t)return 0;
for (int i = h[u], r; ~i; i = ne[i]) {if (e[i] == p) continue;
r = dfs(e[i], u, d + 1, pro * cnt[u]);
// 后果已定：返回
if(r)return r;
}
// 后果未定：持续
return 0;
};
int r = dfs(1, -1, 0, 1);
if(r==1)return 1.0 / res;
return 0;
}工夫复杂度：O(n)
空间复杂度：O(n)
正文完
