1377. T 秒后青蛙的地位

关键词:深度优先

题目起源:1377. T 秒后青蛙的地位 - 力扣(Leetcode)

题目形容

 T深度优先

给你一棵由 n 个顶点组成的无向树,顶点编号从 1 到 n。青蛙从 顶点 1 开始起跳。规定如下:

  • 在一秒内,青蛙从它所在的以后顶点跳到另一个 未拜访 过的顶点(如果它们间接相连)。
  • 青蛙无奈跳回曾经拜访过的顶点。
  • 如果青蛙能够跳到多个不同顶点,那么它跳到其中任意一个顶点上的机率都雷同。
  • 如果青蛙不能跳到任何未拜访过的顶点上,那么它每次跳跃都会停留在原地。

无向树的边用数组 edges 形容,其中 edges[i] = [fromi, toi] 意味着存在一条间接连通 fromitoi 两个顶点的边。

返回青蛙在 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 <= 100edges.length == n - 1edges[i].length == 21 <= ai, bi <= n1 <= t <= 501 <= 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)