目录
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.原文链接
迷宫
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}); }}