迷宫-BFS

别团等shy哥发育

发布于 2023-10-17 14:17:46

2940

发布于 2023-10-17 14:17:46

文章被收录于专栏：全栈开发那些事

1、迷宫(BFS)

1.1 题目描述

这天, 小明在玩迷宫游戏。

迷宫为一个 n×n的网格图, 小明可以在格子中移动, 左上角为

(1,1)

, 右下角为

(n,n)

终点。迷宫中除了可以向上下左右四个方向移动一格以外, 还有m个双向传送门可以使用, 传送门可以连接两个任意格子。

假如小明处在格子

(x_1,y_1)

, 同时有一个传送门连接了格子和

(x_1,y_1)

和

(x_2,y_2)

, 那么小明既可以花费1的步数向上下左右四个方向之一走一格 (不能越过边界), 也可以花费1的步数通过传送门走到格子去

(x_2,y_2)

去。

而对于同一个迷宫, 小明每次进入的初始格子是在这n×n个格子中均匀随机的 (当然运气好可以直接随机到终点), 他想知道从初始格子走到终点的最短步数的期望值是多少。

输入格式

输入共 1+m行, 第一行为两个正整数n,m。

后面m行, 每行四个正整数

x_{i1},y_{i1},x_{i2},y_{i2}

表示第个i传送门连接的两个格子坐标。

输出格式

输出共一行, 一个浮点数表示答案 (请保留两位小数)。

样例输入

2 1
1 1 2 2

样例输出

0.75

样例解释

由于传送门的存在, 从 (1,1) 出发到终点 (2,2) 只需要一步; 而从 (1,2)和 (2,1)出发也只需要向下/右走一步; 从(2,2) 出发需要 0 步。所以步数期望为

\frac{1+1+1+0}{2\times 2} =0.75

。

评测用例规模与约定

对于20%的数据, 保证n,m≤20;

对于100%的数据, 保证

n,m\le 2000;x_{i1},y_{i1},x_{i2},y_{i2}\le n

。

1.2 解题思路

从样例分析可以看出。

期望=\frac{每个点到终点的最短路径之和}{格子的总数}

我们的目的是求出所有点到终点的最短距离之和，我们可以反向思考，使用BFS以终点为起点跑遍整个地图，每次到一个新的位置时，此时到达的步数就是从终点到该点的最短步数(BFS自带最短路效应)。题目中不仅可以上下左右走，还能使用传送门，所以需要记录传送门的位置。 一个位置可能不止一个传送门。

1.3 代码实现

public class Main{
    public static int n;
    public static int m;
    public static Map<Integer, List<int[]>> map = new HashMap<>();//传送门
    public static boolean[][] visited; //访问标记
    public static int[][] dis; //存储每个点到终点的最短步数
    public static int[][] dirs=new int[][]{   //方向
            {-1,0}, //上
            {1,0},  //下
            {0,-1}, //左
            {0,1}   //右
    };
    static StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static void main(String[] args) throws IOException {
        n=nextInt();
        m=nextInt();
        visited=new boolean[n+1][n+1];
        dis=new int[n+1][n+1];
        for (int i = 0; i <m ; i++) {
            int x1=nextInt();
            int y1=nextInt();
            int x2=nextInt();
            int y2=nextInt();
            //双向传送门
            add(x1,y1,x2,y2);
            add(x2,y2,x1,y1);
        }
        //从终点向各个点BFS，找出每个点到终点的最短步数
        LinkedList<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{n,n});
        visited[n][n]=true;
        while(!queue.isEmpty()){
            int[] curr = queue.poll();
            int x=curr[0];
            int y=curr[1];
            //是否可以走传送门
            if(map.containsKey(x*n+y)){
                //可以走的转送们列表
                List<int[]> list = map.get(x * n + y);
                for (int[] g : list) {
                    //(g[0],g[1])是可以传送的点
                    if(!visited[g[0]][g[1]]){
                        queue.offer(g);
                        dis[g[0]][g[1]]=dis[x][y]+1;
                        visited[g[0]][g[1]]=true;
                    }
                }
            }
            //走上下左右
            for (int[] dir : dirs) {
                int newX=x+dir[0];
                int newY = y + dir[1];
                if(newX>=1&&newX<=n&&newY>=1&&newY<=n&&!visited[newX][newY]){
                    queue.offer(new int[]{newX,newY});
                    dis[newX][newY]=dis[x][y]+1;
                    visited[newX][newY]=true;
                }
            }
        }
        //累加各个位置到终点的最小步数
        long ans=0;
        for (int i = 1; i <=n ; i++) {
            for (int j = 1; j <=n ; j++) {
                ans+=dis[i][j];
            }
        }
        System.out.printf("%.2f",ans*1.0/(n*n));
    }
    public static void add(int x1,int y1,int x2,int y2){
        if(!map.containsKey(x1*n+y1)){
            map.put(x1*n+y1,new ArrayList<>());
        }
        map.get(x1*n+y1).add(new int[]{x2,y2});
    }
    public static int nextInt() throws IOException{
        st.nextToken();
        return (int)st.nval;
    }
}

输入一组测试样例