蓝桥杯 BFS 迷宫寻宝
程序员文章站
2022-05-21 15:06:58
...
问题描述
Problem Description
洪尼玛今天准备去寻宝,在一个n*n (n行, n列)的迷宫中,存在着一个入口、一些墙壁以及一个宝藏。由于迷宫是四连通的,即在迷宫中的一个位置,只能走到与它直接相邻的其他四个位置(上、下、左、右)。现洪尼玛在迷宫的入口处,问他最少需要走几步才能拿到宝藏?若永远无法拿到宝藏,则输出-1。
Input
多组测试数据。
每组数据输入第一行为正整数n,表示迷宫大小。
接下来n行,每行包括n个字符,其中字符'.'表示该位置为空地,字符'#'表示该位置为墙壁,字符'S'表示该位置为入口,字符'E'表示该位置为宝藏,输入数据中只有这四种字符,并且'S'和'E'仅出现一次。
n≤1000
Output
输出拿到宝藏最少需要走的步数,若永远无法拿到宝藏,则输出-1。
Sample Input
5
S.#..
#.#.#
#.#.#
#...E
#....
Sample Output
7
Source
福州大学第十五届程序设计竞赛_重现赛
参考代码
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
//存入路的坐标
static Queue<Integer> x = new LinkedList<Integer>();
static Queue<Integer> y = new LinkedList<Integer>();
//地图和状态数组
static char[][] map;
static boolean[][] check;//记录访问状态
//移动方向数组
static int[] dx = {1,-1,0,0};
static int[] dy = {0,0,-1,1};
//记录走过的步数
static int step = 1;
public static void main(String[] args) {
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
map = new char[n][n];//原地图
check = new boolean[n][n];//访问状态矩阵
for (int i = 0; i < map.length; i++) {
String s = sr.next();
map[i] = s.toCharArray();
//创建地图同时获取s的位置
if(s.contains("S")){
x.add(i);
y.add(s.indexOf("S"));
check[x.peek()][y.peek()] = true;
}
}
if (bfs()) {
System.out.println(step);
}else {
System.out.println("-1");
}
}
private static boolean bfs() {
// TODO Auto-generated method stub
//x,y队列里面还有坐标,因为x,y一样长度所以没写
while (!x.isEmpty() ) {
//将新顶点存入临时队列,避免重复搜索(分出步数)
Queue<Integer> tempx = new LinkedList<Integer>();
Queue<Integer> tempy = new LinkedList<Integer>();
while (!x.isEmpty()) {
int tx = x.poll();
int ty = y.poll();
for (int i = 0; i < dx.length; i++) {
int nx =tx + dx[i];
int ny =ty + dy[i];
if (nx >= 0 && ny >= 0 && nx < map.length && ny < map[0].length && map[nx][ny] != '#' && !check[nx][ny]) {
//将新顶点存入临时队列,避免重复搜索(分出步数)
tempx.add(nx);
tempy.add(ny);
check[nx][ny] = true;
//可以访问到目标地点
if (map[nx][ny] == 'E') {
return true;
}
}
}
}
//此时x,y为空
//将收集到的新顶点位置,倒换给x,y
x = tempx;
y = tempy;
//一步已经完成,可以走下一步了
step++;
}
//搜索完成没有找到E
return false;
}
}
上一篇: #997 找到小镇法官
下一篇: 997 找到小镇法官