蓝桥杯——星际旅行(bfs+邻接表优化)

一.题目

分析:只要是能传送过去并且传送次数不为0，就算可以到达，所以这里不能用dfs来，很明显的bfs算法，分层遍历，每一层会消耗一次传送次数，但是本题的数据过大，如果使用邻接矩阵来作为visited数组那么时间复杂度过高，只能通过部分测试用例

1.使用邻接矩阵遍历传送阵时间复杂度为O(n)，假如有50万个星球，那么就需要遍历50万次

2.使用邻接表寻找传送阵时间复杂度为O(1)

二.代码

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
//1:无需package
//2: 类名必须Main, 不可修改

public class Main {
        public static double res;
        static class pair{
        int x;//当前星球
        int y;//剩余传送次数
        public pair(int x,int y)
        {
            this.x = x;
            this.y = y;
        }
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();//n个星球
        int m = scan.nextInt();//m个双向传送门
        int q = scan.nextInt();//q个盲盒
        List<Integer>[] mark = new LinkedList[n+1];
        for (int i = 0; i <mark.length; i++) {
            mark[i] = new LinkedList<>();
        }
        for(int i = 1;i<=m;i++)
        {
            int x = scan.nextInt();
            int y = scan.nextInt();
            mark[x].add(y);//表示可以传送
            mark[y].add(x);
        }
        for(int i = 0;i<q;i++)
        {
            int x = scan.nextInt();//起始星球
            int y = scan.nextInt();//传送次数
            res += bfs(x,y,n,mark);
        }

        System.out.printf("%.2f",(double)res/q);
        scan.close();
    }
    public static int bfs(int index,int cnt,int n,List<Integer>[] mark)
    {
        Queue<pair> queue = new LinkedList<>();
        queue.add(new pair(index,cnt));
        int sum = 0;
        boolean[] map = new boolean[n+1];
        map[index] = true;//已经访问过该星球
        sum++;//表示访问当前星球
        while(!queue.isEmpty())
        {
            //需要分层遍历
            int tmp = queue.size();
            for(int i = 0;i<tmp;i++)
            {
                pair now = queue.poll();
                if(now.y<=0)  break;
                for(int j = 0;j<mark[now.x].size();j++)
                {
                    if(map[mark[now.x].get(j)]!=true)//表示可以访问入队
                    {
                        queue.add(new pair(mark[now.x].get(j),now.y-1));//到达需要消耗一次传送次数
                        map[mark[now.x].get(j)] = true;
                        sum++;
                    }
                }
            }
        }
        return sum;
    }
}

三.问题分析

1.第一次没有考虑到数据过大没有使用邻接表优化，注意使用集合数组前都需要为他们申请空间

2.多次写代码时写错变量，不够专注