数据保证有唯一解，可以考虑BFS、DFS两种遍历方式
广度优先搜索（BFS）
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;
/**
* 【迷宫问题】 - 广度优先搜索（BFS）
*
* 定义一个二维数组 N*M ，如 5 × 5 数组下所示：
* int maze[5][5] = {
* 0, 1, 0, 0, 0,
* 0, 1, 1, 1, 0,
* 0, 0, 0, 0, 0,
* 0, 1, 1, 1, 0,
* 0, 0, 0, 1, 0,
* };
*
* 它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，
* 只能横着走或竖着走，不能斜着走，
* 要求编程序找出从左上角到右下角的路线。
* 入口点为[0,0],既第一格是可以走的路。
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int rows = sc.nextInt();
int columns = sc.nextInt();
// 构建迷宫
int[][] ints = new int[rows][columns];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
ints[i][j] = sc.nextInt();
}
}
// 创建队列以及初始化
ArrayDeque<Node> arrayDeque = new ArrayDeque<>();
arrayDeque.addLast(new Node(0, 0, null));
// 已经检验过节点列表
ArrayList<String> checkedNodeList = new ArrayList<>();
// 终点节点
Node endNode = null;
while (!arrayDeque.isEmpty()) {
// 弹出节点
Node headNode = arrayDeque.pollFirst();
// 判断是否抵达终点
if ((headNode.x == rows - 1) && (headNode.y == columns - 1)) {
endNode = headNode;
break;
}
// 横坐标与纵坐标
int horizontal = headNode.x;
int vertical = headNode.y;
// 校验是否已检查
if (checkedNodeList.contains("" + horizontal + vertical)) {
continue;
}
// 该节点不是终点，则获取该节点所有【值为0】的邻居节点，按照【上下左右】的顺序插入队列
if (horizontal != 0 && ints[horizontal - 1][vertical] == 0) {
arrayDeque.addLast(new Node(horizontal - 1, vertical, headNode)); // 上节点
}
if (horizontal != rows - 1 && ints[horizontal + 1][vertical] == 0) {
arrayDeque.addLast(new Node(horizontal + 1, vertical, headNode)); // 下节点
}
if (vertical != 0 && ints[horizontal][vertical - 1] == 0) {
arrayDeque.addLast(new Node(horizontal, vertical - 1, headNode)); // 左节点
}
if (vertical != columns - 1 && ints[horizontal][vertical + 1] == 0) {
arrayDeque.addFirst(new Node(horizontal, vertical + 1, headNode)); // 右节点
}
// 添加至已校验列表
checkedNodeList.add("" + horizontal + vertical);
}
// 利用栈的特性，从起点位置开始打印
Stack<String> stack = new Stack<>();
while (endNode != null) {
stack.push("(" + endNode.x + "," + endNode.y + ")");
endNode = endNode.father;
}
// 打印路径
while (!stack.isEmpty()) {
System.out.println(stack.pop());
}
}
}
class Node {
int x;
int y;
Node father;
public Node(int x, int y, Node node) {
this.x = x;
this.y = y;
this.father = node;
}
}
深度优先搜索（DFS）
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;
/**
* 【迷宫问题】 - 深度优先搜索（DFS）
*
* 定义一个二维数组 N*M ，如 5 × 5 数组下所示：
* int maze[5][5] = {
* 0, 1, 0, 0, 0,
* 0, 1, 1, 1, 0,
* 0, 0, 0, 0, 0,
* 0, 1, 1, 1, 0,
* 0, 0, 0, 1, 0,
* };
*
* 它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，
* 只能横着走或竖着走，不能斜着走，
* 要求编程序找出从左上角到右下角的路线。
* 入口点为[0,0],既第一格是可以走的路。
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int rows = sc.nextInt();
int columns = sc.nextInt();
// 构建迷宫
int[][] ints = new int[rows][columns];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
ints[i][j] = sc.nextInt();
}
}
// 创建栈
Stack<Point> stack = new Stack<>();
// 创建已检验节点列表
ArrayList<String> checkedPointList = new ArrayList<>();
// 起始节点入栈
stack.push(new Point(0, 0, null));
// 起始节点已检查
checkedPointList.add("" + 0 + 0);
Point endPoint = dfs(ints, stack, checkedPointList);
// 利用栈的特性，从起点位置开始打印
Stack<String> printStack = new Stack<>();
while (endPoint != null) {
printStack.push("(" + endPoint.x + "," + endPoint.y + ")");
endPoint = endPoint.father;
}
// 打印路径
while (!printStack.isEmpty()) {
System.out.println(printStack.pop());
}
}
/**
* 深度遍历
*
* @param ints
* @param stack
* @param checkedPointList
*/
public static Point dfs(int[][] ints, Stack<Point> stack, ArrayList<String> checkedPointList) {
// 获取头节点
Point headPoint = stack.peek();
// 横坐标与纵坐标
int horizontal = headPoint.x;
int vertical = headPoint.y;
// 判断是否抵达终点
if ((horizontal == ints.length - 1) && (vertical == ints[0].length - 1)) {
return headPoint;
}
// 上节点
else if (horizontal != 0 && ints[horizontal - 1][vertical] == 0
&& !checkedPointList.contains("" + (horizontal - 1) + vertical)) {
stack.push(new Point(horizontal - 1, vertical, headPoint));
checkedPointList.add("" + (horizontal - 1) + vertical);
return dfs(ints, stack, checkedPointList);
}
// 下节点
else if (horizontal != ints.length - 1 && ints[horizontal + 1][vertical] == 0
&& !checkedPointList.contains("" + (horizontal + 1) + vertical)) {
stack.push(new Point(horizontal + 1, vertical, headPoint));
checkedPointList.add("" + (horizontal + 1) + vertical);
return dfs(ints, stack, checkedPointList);
}
// 左节点
else if (vertical != 0 && ints[horizontal][vertical - 1] == 0
&& !checkedPointList.contains("" + horizontal + (vertical - 1))) {
stack.push(new Point(horizontal, vertical - 1, headPoint));
checkedPointList.add("" + horizontal + (vertical - 1));
return dfs(ints, stack, checkedPointList);
}
// 右节点
else if (vertical != ints[0].length - 1 && ints[horizontal][vertical + 1] == 0
&& !checkedPointList.contains("" + horizontal + (vertical + 1))) {
stack.push(new Point(horizontal, vertical + 1, headPoint));
checkedPointList.add("" + horizontal + (vertical + 1));
return dfs(ints, stack, checkedPointList);
} else {
// 死胡同，则回溯至上一个节点
stack.pop();
return dfs(ints, stack, checkedPointList);
}
}
}
class Point {
int x;
int y;
Point father;
public Point(int x, int y, Point point) {
this.x = x;
this.y = y;
this.father = point;
}
}
京公网安备 11010502036488号