第十三届蓝桥杯JavaB组国赛E题——迷宫 (AC)

亦凉 2023-09-28 23:19 47阅读 0赞

#### 目录 ####

*  1.迷宫
 *   *  1.问题描述
     *  2.输入格式
     *  3.输出格式
     *  4.样例输入
     *  5.样例输出
     *  6.样例解释
     *  7.数据范围
     *  8.原文链接
 *  2.解题思路
 *  AC\_code

## 1.迷宫 ##

### 1.问题描述 ###

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

迷宫为一个  n × n n \\times n n×n 的网格图, 小明可以在格子中移动, 左上角为  ( 1 , 1 ) (1,1) (1,1), 右 下角  ( n , n ) (n, n) (n,n) 为终点。迷宫中除了可以向上下左右四个方向移动一格以外, 还有  m m m 个双向传送门可以使用, 传送门可以连接两个任意格子。

假如小明处在格子  ( x 1 , y 1 ) \\left(x\_\{1\}, y\_\{1\}\\right) (x1,y1), 同时有一个传送门连接了格子  ( x 1 , y 1 ) \\left(x\_\{1\}, y\_\{1\}\\right) (x1,y1) 和  ( x 2 , y 2 ) \\left(x\_\{2\}, y\_\{2\}\\right) (x2,y2), 那么小明既可以花费 1 的步数向上下左右四个方向之一走一格 (不能 越过边界), 也可以花费 1 的步数通过传送门走到格子  ( x 2 , y 2 ) \\left(x\_\{2\}, y\_\{2\}\\right) (x2,y2) 去。

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

### 2.输入格式 ###

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

后面  m m m 行, 每行四个正整数  x i 1 , y i 1 , x i 2 , y i 2 x\_\{i 1\}, y\_\{i 1\}, x\_\{i 2\}, y\_\{i 2\} xi1,yi1,xi2,yi2表示第  i i i 个传送门连接的两个格 子坐标。

### 3.输出格式 ###

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

### 4.样例输入 ###

2 1  
1 1 2 2

### 5.样例输出 ###

0.75

### 6.样例解释 ###

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

### 7.数据范围 ###

n , m ≤ 2000 ; x i 1 , y i 1 , x i 2 , y i 2 ≤ n n, m \\leq 2000 ; x\_\{i 1\}, y\_\{i 1\}, x\_\{i 2\}, y\_\{i 2\} \\leq n n,m≤2000;xi1,yi1,xi2,yi2≤n 。

### 8.原文链接 ###

[迷宫][Link 1]

## 2.解题思路 ##

可能有些同学刚开始并不知道期望该如何去求，但其实样例已经给了我们很明确的解释。期望等于每个点到终点的最短路径之和，再除以格子的总数。  
  那么很明显这个问题是需要我们求出所有点到终点的距离之和，所以我们反向思考，使用 B F S BFS BFS以终点为起点跑遍整个地图,每次到一个新的位置时，此时到达的步数就是从终点到该点的最短步数，反过来也是从该点到终点的最短步数。为什么一定会是最短呢？因为 B F S BFS BFS自带最短路效应。  
  当然题目不仅是可以上下左右走的，也可以使用魔法传送门，所以我们也需要去记录有哪些传送门。这里需要注意的是，**一个位置可能不止一扇传送门**。虽然样例只有一扇，但我们需要多加考虑，题目并未说明每个位置最多只有一扇传送门，这是一个该题最容易被忽略的地方。  
  讲一下代码细节：题意的左上角坐标是从 ( 1 , 1 ) (1,1) (1,1)开始，我将其更改为 \[ 0 , 0 \] \[0,0\] \[0,0\]，为了方便使用整数映射二维坐标，这是一个常用的技巧。其余代码则为朴素的 B F S BFS BFS模板。

## AC\_code ##

import java.util.*;
    
    public class Main {
        
        static int N=2010;
        static Map<Integer,List<int[]>> map=new HashMap<>();
        static boolean[][] st=new boolean[N][N];
        static int[] dx={
        0,0,-1,1};
        static int[] dy={
        1,-1,0,0};
        static int n,m;
        public static void main(String[] args) {
        
            Scanner sc=new Scanner(System.in);
            n=sc.nextInt();
            m=sc.nextInt();
            for (int i = 0; i < m; i++) {
        
                int x1=sc.nextInt()-1;
                int y1=sc.nextInt()-1;
                int x2=sc.nextInt()-1;
                int y2=sc.nextInt()-1;
                add(x1,y1,x2,y2);
                add(x2,y2,x1,y1);
            }
            Queue<int[]> queue=new LinkedList<>();
            queue.offer(new int[]{
        n-1,n-1});
            st[n-1][n-1]=true;
            //累计答案
            int ans=0;
            //计算层数
            int x=0;
            while (!queue.isEmpty()){
        
                int size=queue.size();
                while (size-->0){
        
                    int[] curr=queue.poll();
                    int a=curr[0],b=curr[1];
                    //累加答案
                    ans+=x;
                    if (map.containsKey(a*n+b)){
        
                        List<int[]> list=map.get(a*n+b);
                        for (int[] g:list){
        
                            if (!st[g[0]][g[1]]){
        
                                queue.offer(g);
                                st[g[0]][g[1]]=true;
                            }
                        }
                    }
                    for (int i = 0; i < 4; i++) {
        
                        int newX=a+dx[i];
                        int newY=b+dy[i];
                        if (newX>=0&&newX<n&&newY>=0&&newY<n&&!st[newX][newY]){
        
                            queue.offer(new int[]{
        newX,newY});
                            st[newX][newY]=true;
                        }
                    }
                }
                x++;
            }
            System.out.printf("%.2f",ans*1.0/(n*n));
        }
        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});
        }
    }

[Link 1]: https://www.lanqiao.cn/problems/2222/learning/