LeetCode 搜索[L1]

1377. T 秒后青蛙的位置

题目真正看懂了一小时，连带着三四次递归炸了。。

这只青蛙有个特点，它跳到了target，假如还有顶点可以访问，他就会继续跳下去。

//刚开始以为跳到target然后时间有多的话就原地跳。。

因为它可以一直往下跳，所以路程上的点的概率是可以为0的，因此在概率转移的时候就要减去当前点的概率，把概率转移到下一个点上

需要target点的概率，要图的所有路径都便遍历一遍，回溯，减枝，解决。

class Solution {
    double pr[110];
    int book[110];
    map<int,vector<int> >tree;
    void dfs(int cur,int t)
    {
        if(t<=0) return ;//时间到了就退出
        int res=0;
        for(int i=0;i<tree[cur].size();i++)
        {
            if(book[tree[cur][i]]==0)
            res++;
        }
        if(res==0) return ;//没地方走了也退出
        double p=pr[cur]/res;//当前点的概率
        for(int i=0;i<tree[cur].size();i++)
        {
            int next=tree[cur][i];
            if(book[next]==0)
            {
                
                book[next]=1;
                pr[cur]=0;
                pr[next]+=p;
                dfs(next,t-1);
                book[next]=0;
            }
        }
    }
public:
    double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
        memset(book,0,sizeof book);
        memset(pr,0,sizeof pr);
        pr[1]=1.0,book[1]=1;
        for(auto edge:edges)
        {
            tree[edge[0]].push_back(edge[1]);
            tree[edge[1]].push_back(edge[0]);
        }
        dfs(1,t);
        return pr[target];
    }
};

也可以用BFS，第二层开始不要把父节点的时间和数目算进去👌
//这里又炸半天/(ㄒoㄒ)/~~

class Solution {
    double pr[110];
    int minute[110];
    map<int,vector<int> >tree;
    void bfs(int v,int t)
    {
        queue<int>q;
        q.push(1);
        minute[1]=0;
        pr[1]=1.0;
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            if(minute[u]>=t)
                continue;//超出时间，尝试另外路径
            for(int i=0;i<tree[u].size();i++)
            {
                int v=tree[u][i];
                if(minute[v]>minute[u]+1)
                {
                    minute[v]=minute[u]+1;
                    if(u!=1)
                    pr[v]=pr[u]/(tree[u].size()-1);
                    else
                    pr[v]=pr[u]/tree[u].size();
                    q.push(v);
                }
            }
        }
    }
public:
    double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
        memset(minute,0x3f,sizeof minute);
        memset(pr,0,sizeof pr);
        for(auto edge:edges)
        {
            tree[edge[0]].push_back(edge[1]);
            tree[edge[1]].push_back(edge[0]);
        }
        bfs(1,t);
        if(minute[target]<t)
//青蛙至少可以跳过终点，如果是非叶子节点，跳过头了，返回0
        {
            if(tree[target].size()>1||target==1&&tree[1].size()>0)
//可以是一个非叶子结点，
 //可以仅是一个根节点，就停在根节点
                return 0;
        }
        return pr[target];
    }
};

---