第十三屆藍橋杯JavaB組國賽E題——迷宮 (AC)

目錄

• ​​1.迷宮​​

• ​​1.問題描述​​
• ​​2.輸入格式​​
• ​​3.輸出格式​​
• ​​4.樣例輸入​​
• ​​5.樣例輸出​​
• ​​6.樣例解釋​​
• ​​7.資料範圍​​
• ​​8.原文連結​​

• ​​2.解題思路​​
• ​​AC_code​​

1.迷宮

1.問題描述

  這天, 小明在玩迷宮遊戲。

的網格圖, 小明可以在格子中移動, 左上角為 , 右 下角 為終點。迷宮中除了可以向上下左右四個方向移動一格以外, 還有

, 同時有一個傳送門連接配接了格子 和 , 那麼小明既可以花費 1 的步數向上下左右四個方向之一走一格 (不能 越過邊界), 也可以花費 1 的步數通過傳送門走到格子

2.輸入格式

輸入共 行, 第一行為兩個正整數

後面 行, 每行四個正整數 表示第

3.輸出格式

輸出共一行, 一個浮點數表示答案 (請保留兩位小數)。

4.樣例輸入

2 1

1 1 2 2

5.樣例輸出

0.75

6.樣例解釋

由于傳送門的存在, 從 出發到終點 隻需要一步; 而從 和 出發也隻需要向下/右走一步; 從 出發需要 0 步。是以步數期望為

7.資料範圍

8.原文連結

2.解題思路

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});
    }
}