1、迷宫(BFS)
1.1 题目描述
这天, 小明在玩迷宫游戏。
迷宫为一个 n×n的网格图, 小明可以在格子中移动, 左上角为
, 右下角 为
终点。迷宫中除了可以向上下左右四个方向移动一格以外, 还有m个双向传送门可以使用, 传送门可以连接两个任意格子。
假如小明处在格子
, 同时有一个传送门连接了格子和
和
, 那么小明既可以花费1的步数向上下左右四个方向之一走一格 (不能越过边界), 也可以花费1的步数通过传送门走到格子去
去。
而对于同一个迷宫, 小明每次进入的初始格子是在这n×n个格子中均匀随机的 (当然运气好可以直接随机到终点), 他想知道从初始格子走到终点的最短步数的期望值是多少。
输入格式
输入共 1 m行, 第一行为两个正整数n,m。
后面m行, 每行四个正整数
表示第个i传送门连接的两个格子坐标。
输出格式
输出共一行, 一个浮点数表示答案 (请保留两位小数)。
样例输入
代码语言：javascript复制2 1
1 1 2 2 样例输出
代码语言：javascript复制0.75样例解释
由于传送门的存在, 从 (1,1) 出发到终点 (2,2) 只需要一步; 而从 (1,2)和 (2,1)出发也只需要向下/右走一步; 从(2,2) 出发需要 0 步。所以步数期望为
。
评测用例规模与约定
对于20%的数据, 保证n,m≤20;
对于100%的数据, 保证
。
1.2 解题思路
从样例分析可以看出。
我们的目的是求出所有点到终点的最短距离之和，我们可以反向思考，使用BFS以终点为起点跑遍整个地图，每次到一个新的位置时，此时到达的步数就是从终点到该点的最短步数(BFS自带最短路效应)。题目中不仅可以上下左右走，还能使用传送门，所以需要记录传送门的位置。
一个位置可能不止一个传送门。
1.3 代码实现
代码语言：javascript复制public class Main{
public static int n;
public static int m;
public static Map<Integer, List<int[]>> map = new HashMap<>();//传送门
public static boolean[][] visited; //访问标记
public static int[][] dis; //存储每个点到终点的最短步数
public static int[][] dirs=new int[][]{ //方向
{-1,0}, //上
{1,0}, //下
{0,-1}, //左
{0,1} //右
};
static StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
public static void main(String[] args) throws IOException {
n=nextInt();
m=nextInt();
visited=new boolean[n 1][n 1];
dis=new int[n 1][n 1];
for (int i = 0; i <m ; i ) {
int x1=nextInt();
int y1=nextInt();
int x2=nextInt();
int y2=nextInt();
//双向传送门
add(x1,y1,x2,y2);
add(x2,y2,x1,y1);
}
//从终点向各个点BFS，找出每个点到终点的最短步数
LinkedList<int[]> queue = new LinkedList<>();
queue.offer(new int[]{n,n});
visited[n][n]=true;
while(!queue.isEmpty()){
int[] curr = queue.poll();
int x=curr[0];
int y=curr[1];
//是否可以走传送门
if(map.containsKey(x*n y)){
//可以走的转送们列表
List<int[]> list = map.get(x * n y);
for (int[] g : list) {
//(g[0],g[1])是可以传送的点
if(!visited[g[0]][g[1]]){
queue.offer(g);
dis[g[0]][g[1]]=dis[x][y] 1;
visited[g[0]][g[1]]=true;
}
}
}
//走上下左右
for (int[] dir : dirs) {
int newX=x dir[0];
int newY = y dir[1];
if(newX>=1&&newX<=n&&newY>=1&&newY<=n&&!visited[newX][newY]){
queue.offer(new int[]{newX,newY});
dis[newX][newY]=dis[x][y] 1;
visited[newX][newY]=true;
}
}
}
//累加各个位置到终点的最小步数
long ans=0;
for (int i = 1; i <=n ; i ) {
for (int j = 1; j <=n ; j ) {
ans =dis[i][j];
}
}
System.out.printf("%.2f",ans*1.0/(n*n));
}
public 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});
}
public static int nextInt() throws IOException{
st.nextToken();
return (int)st.nval;
}
}输入一组测试样例
这个代码是可以AC的
