1377.T秒后青蛙的位置

链接：1377.T秒后青蛙的位置
难度：Hard
标签：树、深度优先搜索、广度优先搜索、图
简介：返回青蛙在 t 秒后位于目标顶点 target 上的概率。

题解 1 - cpp

• 编辑时间：2023-05-24
• 执行用时：24ms
• 内存消耗：14.5MB
• 编程语言：cpp
• 解法介绍：dfs遍历，因为每个点之间都连通，判断当青蛙到目标点后是否还能继续向外跳。

class Solution {
public:
    double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
        vector<vector<int>> nodes(n + 1);
        for (auto &e : edges) {
            nodes[e[0]].push_back(e[1]);
            nodes[e[1]].push_back(e[0]);
        }
        vector<bool> used(n + 1, false);
        used[1] = true;
        function<double(int, int)> dfs = [&](int cur, int t) {
            int sum = 0;
            for (auto &next : nodes[cur]) {
                if (!used[next]) sum += 1;
            }
            if (cur == target || t == 0) {
                return cur == target && (t == 0 || sum == 0) ? 1.0 : 0.0;
            }
            for (auto &next : nodes[cur]) {
                if (!used[next]) {
                    used[next] = true;
                    auto res = dfs(next, t - 1);
                    used[next] = false;
                    if (res != 0.0) return res / sum;
                }
            }
            return 0.0;
        };
        return dfs(1, t);
    }
};

题解 2 - python

• 编辑时间：2023-05-24
• 执行用时：52ms
• 内存消耗：16.4MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        nodes = [[] for _ in range(n + 1)]
        for e in edges:
            nodes[e[0]].append(e[1])
            nodes[e[1]].append(e[0])
        used = [False for _ in range(n + 1)]
        used[1] = True
        def dfs(cur: int, t: int) -> float:
            sum = 0
            for next in nodes[cur]:
                if not used[next]:
                    sum += 1
            if cur == target or t == 0:
                return 1 if cur == target and (t == 0 or sum == 0) else 0
            for next in nodes[cur]:
                if not used[next]:
                    used[next] = True
                    res = dfs(next, t - 1)
                    used[next] = False
                    if res != 0:
                        return res / sum
            return 0
        return dfs(1, t)

题解 3 - rust

• 编辑时间：2023-05-24
• 执行用时：4ms
• 内存消耗：1.9MB
• 编程语言：rust
• 解法介绍：同上。

fn dfs(nodes: &Vec<Vec<usize>>, used: &mut Vec<bool>, target: usize, cur: usize, t: i32) -> f64 {
let mut sum: f64 = 0.0;
for next in &nodes[cur] {
    if !used[*next] {
        sum += 1.0;
    }
}
if cur == target || t == 0 {
    if cur == target && (t == 0 || sum == 0.0) {
        1.0
    } else {
        0.0
    }
} else {
    for next in &nodes[cur] {
        if !used[*next] {
            used[*next] = true;
            let res = dfs(nodes, used, target, *next, t - 1);
            used[*next] = false;
            if res != 0.0 {
                return res / sum;
            }
        }
    }
    0.0
}
}
impl Solution {
    pub fn frog_position(n: i32, edges: Vec<Vec<i32>>, t: i32, target: i32) -> f64 {
        let n = n as usize;
        let mut nodes: Vec<Vec<usize>> = vec![vec![]; n + 1];
        for e in edges {
            let (e0, e1) = (e[0] as usize, e[1] as usize);
            nodes[e0].push(e1);
            nodes[e1].push(e0);
        }
        let mut used = vec![false; n + 1];
        used[1] = true;
        dfs(&nodes, &mut used, target as usize, 1, t)
    }
}