侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【BFS】迷宫【蓝桥杯】

GabrielxD
2023-04-24 / 0 评论 / 0 点赞 / 105 阅读 / 1,100 字
温馨提示:
本文最后更新于 2023-04-24,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

迷宫 - 蓝桥云课


问题描述

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

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

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

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

输入格式

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

后面 mm 行, 每行四个正整数 xi1,yi1,xi2,yi2x_{i 1}, y_{i 1}, x_{i 2}, y_{i 2} 表示第 ii 个传送门连接的两个格 子坐标。

输出格式

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

样例输入

2 1
1 1 2 2

样例输出

0.75

样例解释

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

评测用例规模与约定

对于 20%20 \% 的数据, 保证 n,m20n, m \leq 20 ;

对于 100%100 \% 的数据, 保证 n,m2000;xi1,yi1,xi2,yi2nn, m \leq 2000 ; x_{i 1}, y_{i 1}, x_{i 2}, y_{i 2} \leq n

运行限制

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

解题

方法一:BFS

思路

把迷宫右下角 (n,n)(n, n) 定为起点做 BFS ,第一次到达某一格 (x,y)(x, y) 的步数即为 (x,y)(n,n)(x,y) \to (n, n) 的最短步数 dists[x][y]dists[x][y] ,那么最终的期望值即为 x=1n(y=1ndists[x][y])n×n\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));
    }
}

0

评论区