当前位置：网站首页>【英雄哥六月集训】第 27天: 图

class Solution {
    
    int maxn = 10010;
    List<List<Edge>> edge = new ArrayList<List<Edge>>(maxn);
    class Edge{
    
        int to;
        double val;
        Edge(){
    
        }

        Edge(int t,double v){
    
            this.to=t;
            this.val=v;
        }
    }

    public double bfs(int start,int end){
    
        double[] dis = new double[maxn];
        int i;
        for(i=0;i<maxn;++i){
    
            dis[i]=0.00d;
        }
        dis[start]=1.00d;
        Queue<Integer> q = new ArrayDeque<Integer>();
        q.add(start);
        while(!q.isEmpty()){
    
            Integer u = q.remove();
            int len = edge.get(u).size();
            for(i=0;i<len;++i){
    
                int v = edge.get(u).get(i).to;
                double d = dis[u]*(edge.get(u).get(i).val);

                if(d>dis[v]){
    
                    dis[v]=d;
                    q.add(v);
                }
            }
        }
        return dis[end];
    }
    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
    
        int i;
        for(i=0;i<maxn;++i){
    
            edge.add(new ArrayList<Edge>());
        }
        for(i=0;i<edges.length;++i){
    
            if(succProb[i]<=0){
    
                continue;
            }
            int u = edges[i][0];
            int v = edges[i][1];
            double w = succProb[i];

            edge.get(u).add(new Edge(v,w));
            edge.get(v).add(new Edge(u,w));
            
        }
        return bfs(start,end);
    }
}

二、信物传送

LCP 56. 信物传送

class Solution {
    
    int[][] dir = new int[][]{
    
        {
    -1,0},{
    0,1},{
    1,0},{
    0,-1}
    };
    public int conveyorBelt(String[] matrix, int[] start, int[] end) {
    
        int i,j;
        int m=matrix.length;
        int n = matrix[0].length();
        int[][] grid = new int [110][110];
        for(i=0;i<m;i++){
    
            for(j=0;j<n;j++){
    
                if(matrix[i].charAt(j)=='^'){
    
                    grid[i][j]=0;
                }
                else if(matrix[i].charAt(j)=='>'){
    
                    grid[i][j]=1;
                }
                else if(matrix[i].charAt(j)=='v'){
    
                    grid[i][j]=2;
                }
                else if(matrix[i].charAt(j)=='<'){
    
                    grid[i][j]=3;
                }
            }
        }
        int u = start[0]*n+start[1];
        int[] dis = new int[10010];
        for(i=0;i<n*m;++i){
    
            dis[i]=100000000;
        }
        dis[u]=0;
        Deque<Integer> q = new ArrayDeque<Integer>();
        q.add(u);
        while(!q.isEmpty()){
    
            Integer f = q.remove();
            int x = f/n;
            int y = f%n;
            for(i=0;i<4;++i){
    
                int tx = x+dir[i][0];
                int ty = y+dir[i][1];

                if(tx<0||ty<0||tx==m||ty==n){
    
                    continue;
                }
                int next = tx*n+ty;
                int nextd = dis[f]+((grid[x][y]==i?0:1));
                if(nextd < dis[next]){
    
                    dis[next] = nextd;
                    q.add(next);
                }
            }
        }
        return dis[end[0]*n+end[1]];

        
    }
}

三、 T 秒后青蛙的位置

1377. T 秒后青蛙的位置

class Solution {
    
    int maxn = 110;
    List<List<Integer>> e = new ArrayList<List<Integer>>(maxn);
    double ans = 0.00d;
    public void inite(){
    
        for(int i=0;i<maxn;i++){
    
            e.add(new ArrayList<Integer>());
        }
    }
    public void dfs(int u,int fat,double p,int step,int maxstep,int target){
    
        int i,cnt=0;
        for(i =0; i<e.get(u).size(); ++i){
    
            if(e.get(u).get(i)!=fat){
    
                ++cnt;
            }
        }
        if(step <= maxstep){
    
            if(u==target){
    
                if(cnt ==0 && step <= maxstep){
    
                    ans = p;
                } else if(cnt>=1 && step == maxstep){
    
                    ans = p;
                }
            }
        }
        if(step == maxstep){
    
            return ;
        }

        for(i=0; i<e.get(u).size(); ++i){
    
            if(e.get(u).get(i)!=fat){
    
                dfs(e.get(u).get(i),u,p*1.0/cnt,step+1,maxstep,target);
            }
        }
    }
    public double frogPosition(int n, int[][] edges, int t, int target) {
    
        inite();
        int i;
        for(i=0; i<edges.length; ++i){
    
            int u = edges[i][0];
            int v = edges[i][1];

            e.get(u).add(v);
            e.get(v).add(u);
        }

        dfs(1,0,1,0,t,target);
        return ans;
    }
}