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

1.迷宫

1.问题描述

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

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

  假如小明处在格子 $\left(x_1,y_1\right)$, 同时有一个传送门连接了格子 $\left(x_1,y_1\right)$ 和 $\left(x_2,y_2\right)$, 那么小明既可以花费 1 的步数向上下左右四个方向之一走一格 (不能 越过边界), 也可以花费 1 的步数通过传送门走到格子 $\left(x_2,y_2\right)$ 去。

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

2.输入格式

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

后面 $m$ 行, 每行四个正整数 $x_{i1},y_{i1},x_{i2},y_{i2}$表示第 $i$ 个传送门连接的两个格 子坐标。

3.输出格式

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

4.样例输入

2 1
1 1 2 2

5.样例输出

0.75

6.样例解释

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

7.数据范围

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

8.原文链接

迷宫

2.解题思路

  可能有些同学刚开始并不知道期望该如何去求，但其实样例已经给了我们很明确的解释。期望等于每个点到终点的最短路径之和，再除以格子的总数。
  那么很明显这个问题是需要我们求出所有点到终点的距离之和，所以我们反向思考，使用$BFS$以终点为起点跑遍整个地图,每次到一个新的位置时，此时到达的步数就是从终点到该点的最短步数，反过来也是从该点到终点的最短步数。为什么一定会是最短呢？因为$BFS$自带最短路效应。
  当然题目不仅是可以上下左右走的，也可以使用魔法传送门，所以我们也需要去记录有哪些传送门。这里需要注意的是，一个位置可能不止一扇传送门。虽然样例只有一扇，但我们需要多加考虑，题目并未说明每个位置最多只有一扇传送门，这是一个该题最容易被忽略的地方。
  讲一下代码细节：题意的左上角坐标是从$(1,1)$开始，我将其更改为$[0,0]$，为了方便使用整数映射二维坐标，这是一个常用的技巧。其余代码则为朴素的$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});
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62