迷宫

题目描述

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

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

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

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

输出描述

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

输出描述

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

样例

样例输入

2 1
1 1 2 2

样例输出

0.75

样例解释

计算的是一个期望值，是矩阵中所有节点的最短路到终点的总和/ 矩阵大小。

思路

边权为1，还是可以使用bfs，不过由于传送门的存在，需要进行特殊判断。

代码实现

import java.util.*;public class Main{public static class pair{int first;int second;public pair(int first, int second) {this.first = first;this.second = second;}}static int[][] dir = {{1, 0},{-1, 0},{0, 1},{0, -1}};public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(), m = sc.nextInt();int[][] matrix = new int[n + 1][n + 1];boolean[][] vis = new boolean[n + 1][n + 1];List<pair> list[][] = new ArrayList[n + 1][n + 1];for(int i = 0; i < m; i++) {int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt(), d = sc.nextInt();if(list[a][b] == null) list[a][b] = new ArrayList<>();if(list[c][d] == null) list[c][d] = new ArrayList<>();list[a][b].add(new pair(c, d));list[c][d].add(new pair(a, b));}matrix[n][n] = 0;vis[n][n] = true; Queue<pair> queue = new ArrayDeque<>();queue.offer(new pair(n, n));while(!queue.isEmpty()) {pair cur = queue.poll();if(list[cur.first][cur.second] != null) {for(pair c : list[cur.first][cur.second]) {if(!vis[c.first][c.second]) {vis[c.first][c.second] = true;matrix[c.first][c.second] = matrix[cur.first][cur.second] + 1;queue.offer(c);}}}for(int[] d : dir) {int x = cur.first + d[0];int y = cur.second + d[1];if(0 < x && x <= n && 0 < y && y <= n && !vis[x][y]) {vis[x][y]= true; matrix[x][y] = matrix[cur.first][cur.second] + 1; queue.offer(new pair(x, y));}}}long sum = 0;for(int[] r : matrix) {for(int c : r)sum += c;}System.out.printf("%.2f", (double)((sum * 1.0)  / (n * n)));sc.close();}
}