永泰县住房和城乡建设局网站,网站开发付款方式和比例,企业网站模板seo,做网站软件miscrosoft迷宫
题目描述
这天, 小明在玩迷宫游戏。
迷宫为一个 nn 的网格图, 小明可以在格子中移动, 左上角为 (1,1), 右 下角 (n,n) 为终点。迷宫中除了可以向上下左右四个方向移动一格以外, 还有 m 个双向传送门可以使用, 传送门可以连接两个任意格子。
假如小明处在格子 (x1,y1)(…迷宫
题目描述
这天, 小明在玩迷宫游戏。
迷宫为一个 n×n 的网格图, 小明可以在格子中移动, 左上角为 (1,1), 右 下角 (n,n) 为终点。迷宫中除了可以向上下左右四个方向移动一格以外, 还有 m 个双向传送门可以使用, 传送门可以连接两个任意格子。
假如小明处在格子 (x1,y1)(x_1,y _1)(x1,y1), 同时有一个传送门连接了格子 (x1,y1)(x_1,y_1)(x1,y1) 和 (x2,y2)(x_2,y_2)(x2,y2), 那么小明既可以花费 1 的步数向上下左右四个方向之一走一格 (不能 越过边界), 也可以花费 1 的步数通过传送门走到格子 (x2,y2)(x_2,y_2 )(x2,y2) 去。
而对于同一个迷宫, 小明每次进入的初始格子是在这 n×n 个格子中均匀随 机的 (当然运气好可以直接随机到终点), 他想知道从初始格子走到终点的最短 步数的期望值是多少。
输出描述
输入共 1m 行, 第一行为两个正整数 n,m 。后面 m 行, 每行四个正整数 ,xi1,yi1,xi2,yi2x_{i1},y_{i1},x_{i2},y_{i2}xi1,yi1,xi2,yi2表示第 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];Listpair 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; Queuepair 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();}
}
