【BFS】迷宫【蓝桥杯】

题目

问题描述

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

迷宫为一个 $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$ 个格子中均匀随机的 (当然运气好可以直接随机到终点), 他想知道从初始格子走到终点的最短步数的期望值是多少。

输入格式

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

后面 $m$ 行, 每行四个正整数 $x_{i 1}, y_{i 1}, x_{i 2}, y_{i 2}$ 表示第 $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 \leq 20$ ;

对于 $100 \%$ 的数据, 保证 $n, m \leq 2000 ; x_{i 1}, y_{i 1}, x_{i 2}, y_{i 2} \leq n$ 。

运行限制

最大运行时间：3s
最大运行内存: 512M

解题

方法一：BFS

思路

把迷宫右下角 $(n, n)$ 定为起点做 BFS ，第一次到达某一格 $(x, y)$ 的步数即为 $(x,y) \to (n, n)$ 的最短步数 $dists[x][y]$ ，那么最终的期望值即为 $\frac{\sum_{x=1}^{n}{(\sum_{y=1}^{n}{dists[x][y]})}}{n \times n}$ 。

注意：传送门是双向的，且一个格子可能有多个传送门，所以每个点上的传送门要用列表来存。

代码

import java.util.*;
import java.io.*;

public class Main {
    static int[][] DIRS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    static int n, m;
    static List<int[]>[][] pts;
    static int[][] dists;

    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        n = in.nextInt(); m = in.nextInt();
        pts = new ArrayList[n + 1][n + 1];
        while (m-- > 0) {
            int x1 = in.nextInt(), y1 = in.nextInt();
            int x2 = in.nextInt(), y2 = in.nextInt();
            if (pts[x1][y1] == null) pts[x1][y1] = new ArrayList<>();
            if (pts[x2][y2] == null) pts[x2][y2] = new ArrayList<>();
            pts[x1][y1].add(new int[]{x2, y2});
            pts[x2][y2].add(new int[]{x1, y1});
        }
        dists = new int[n + 1][n + 1];
        for (int[] arr : dists) Arrays.fill(arr, -1);
        Queue<int[]> que = new LinkedList<>();
        que.offer(new int[]{n, n});
        dists[n][n] = 0;
        int d = 1;
        while (!que.isEmpty()) {
            int sz = que.size();
            while (sz-- > 0) {
                int[] curr = que.poll();
                int x = curr[0], y = curr[1];
                for (int[] DIR : DIRS) {
                    int nx = x + DIR[0], ny = y + DIR[1];
                    if (nx <= 0 || nx > n || ny <= 0 || ny > n || dists[nx][ny] != -1) continue;
                    dists[nx][ny] = d;
                    que.offer(new int[]{nx, ny});
                }
                if (pts[x][y] != null) {
                    for (int[] pos : pts[x][y]) {
                        int nx = pos[0], ny = pos[1];
                        if (dists[nx][ny] != -1) continue;
                        dists[nx][ny] = d;
                        que.offer(pos);
                    }
                }
            }
            ++d;
        }
        double sum = 0.0;
        for (int x = 1; x <= n; ++x) {
            for (int y = 1; y <= n; ++y) sum += dists[x][y];
        }
        System.out.printf("%.2f\n", sum / (n * n));
    }
}

目录CONTENT

【BFS】迷宫【蓝桥杯】

题目

解题

方法一：BFS

思路

代码

评论区