2753:走迷宫（Java）（深度优先搜索，广度优先搜索）
目录
1.题目描述：
2.Java答案：
深度优先：
广度优先：
3.解析：
深度优先：
广度优先：
1.题目描述：
2.Java答案：
深度优先：
import java.util.Scanner;
public class Main {
public static int[][] directions = {{1,0}, {-1,0}, {0,1}, {0,-1}};
public static int h = Integer.MAX_VALUE;
public static void main(String[] args) {
Scanner v = new Scanner(System.in);
int n = v.nextInt();
int m = v.nextInt();
v.nextLine();
char [][] a = new char[n][m];
boolean[][]aa = new boolean[n][m];
for (int i = 0; i < n; i++) {
String g = v.nextLine();
for (int j = 0; j < m; j++) {
a[i][j] = g.charAt(j);
}
}
get(a, 0, 0, n - 1, m - 1, aa, 1);
System.out.println(h);
}
private static void get(char[][] a, int i, int j, int ii, int jj, boolean[][] aa, int hh) {
if (i >= 0 && i <= ii && j >= 0 && j <= jj && a[i][j] == '.' && !aa[i][j]){
aa[i][j] = true;
if (i == ii && j == jj){
h = Math.min(h , hh);
}
for (int [] k : directions){
get(a, i + k[0], j + k[1], ii, jj, aa, hh + 1);
}
}
}
}广度优先：
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static int[][] directions = {{1,0}, {-1,0}, {0,1}, {0,-1}};
public static int h = Integer.MAX_VALUE;
public static class Node {
int x;
int y;
int n;
Node(int x, int y, int n){
this.x = x;
this.y = y;
this.n = n;
}
}
public static void main(String[] args) {
Scanner v = new Scanner(System.in);
int n = v.nextInt();
int m = v.nextInt();
v.nextLine();
char [][] a = new char[n][m];
boolean[][]aa = new boolean[n][m];
for (int i = 0; i < n; i++) {
String g = v.nextLine();
for (int j = 0; j < m; j++) {
a[i][j] = g.charAt(j);
}
}
get(a, n - 1, m - 1, aa);
System.out.println(h);
}
private static void get(char[][] a, int ii, int jj, boolean[][] aa) {
Queue<Node> queue = new LinkedList<>();
queue.add(new Node(0, 0, 1));
aa[0][0] = true;
while (!queue.isEmpty()){
Node l = queue.poll();
if (l.x == ii && l.y == jj){
h = Math.min(h, l.n);
}
for (int [] k : directions){
int newX = l.x + k[0];
int newY = l.y + k[1];
if (newX >= 0 && newX <= ii && newY >= 0 && newY <= jj && a[newX][newY] == '.' && !aa[newX][newY]){
aa[newX][newY] = true;
queue.add(new Node(newX, newY, l.n + 1));
}
}
}
}
}3.解析：
深度优先：
main 方法
- 首先利用 Scanner 接收用户的输入数据并确定矩阵的行数 n 和列数 m。
- 初始化两个二维数组：一个是字符类型的二维数组 a 来存储原始数据 另一个是布尔类型的二维数组 aa 来记录哪些位置已被访问过。
- 采用循环结构逐行读取输入并将其赋值给 a 数组中的相应位置。
- 调用 get 方法从起始点 (0, 0) 开始 并设定目标点为 (n-1, m-1) 初始路径长度设为 1 进行深度优先搜索。
- 遍历所有可能路径后计算并输出找到的最短路径长度 h。
get 方法（深度优先搜索的核心方法）
- 首先确认当前位置 (i, j) 在矩阵范围内，并且是 . 且尚未被访问。
- 将当前位置标记为已访问状态。
- 如果当前位置与目标位置 (ii, jj) 相同，则比较当前路径长度 hh 和现有的最短路径长度 h，并将 h 更新为其中较小值。
- 针对四个方向（上、下、左、右），递归调用 get 方法，并将当前位置向这些方向移动一步，并增加路径长度 hh。
三、变量和常量
directions 表示一个二维整数数组的方向偏移量；它存储了四个方向的偏移量——向下、向上、向右、向左移动。
h 初始化为 Integer.MAX\_VALUE ，用于存储最短路径长度。
aa 是一个标记访问位置的二维布尔数组。
四、深度优先搜索的过程
广度优先：
main 方法
首先使用 Scanner 从用户处获取矩阵的行数 n 和列数 m 这一步骤完成之后 我们接下来初始化了一个字符数组 a 并建立与之对应的布尔数组 aa 它们分别用于存储矩阵中的字符数据以及标记哪些位置已经被访问过
然后我们开始遍历每行输入并将其逐一存入到 a 数组中
随后调用 get 方法来计算并确定最短路径的具体长度 最后将计算得到的结果以标准格式输出
Node 类
该类为每个节点进行了定义，并包含三个属性：x和y表示其在二维矩阵中的坐标位置；其中n代表从起始点到当前节点所经过的路径长度。
get 方法
初始化一个队列 queue 用于存储待处理的节点。
将起始点 (0, 0) 添加到 queue 中并标记为已访问。
只要 queue 不为空时：
取出当前 queue 的第一个节点 l。
若当前处理的节点即为目标点 (ii, jj)，则更新最短路径长度 h。
检查四个相邻的方向：
对于每一个方向检查后得到的新坐标位置：
如果新坐标位于矩阵范围内且对应字符为 '.' 并未被访问过，
则将新坐标添加到 queue 中并标记为已访问。
三、变量和常量
- 方向（directions）：一个二维整数数组，记录了上下左右四个方向的偏移量。
- h（h）：初始化为Integer的最大值（MAX_VALUE），用于记录最短路径的长度。
- aa（aa）：一个二维布尔数组，在该矩阵中的各个位置上标记是否已经被访问过。
四、广度优先搜索的过程
广度优先策略从起始点开始执行操作首先探索与起始点仅隔一步的所有节点随后依次扩展距离起始点两步三步直至覆盖整个搜索空间