欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

蓝桥杯 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;
}
}