- 迷宫项目
- 1.项目介绍
- 2.项目功能
- 3.项目结果演示
- 4.项目实现分析
- 5.迷宫完整代码
一个网格迷宫由n行m列的单元格组成，每个大院要么是空地（用0表示），要么是障碍物（用1表示）。你的任务是找一条从起点到终点的移动序列，其中只能上下左右移动到相邻单元格。任何时候都不能在有障碍物的单元格中，也不能走到迷宫之外。起点为左上角，终点为右下角。
2.项目功能解决迷宫路径查找问题，寻找一条从左上角迷宫入口到右下角迷宫出口的一条有效路径，0代表可走，1代表不能行走，找到请输出最终的迷宫和路径信息，找不到请输出不存在有效路径。
3.项目结果演示 4.项目实现分析1）迷宫由n行m列的单元格组成。所以要定义一个二维数组。
2）迷宫要设置空地和障碍物，用0表示空地，1表示障碍物，假设迷宫是一个3 × 3的单元格，每个单元格里要放0和1，那么简单的设计成一个整型二维数组可以吗？我们除了在每个单元格中要设置0和1外，还要额外考虑当前单元格的东、南、西、北四个方向是否可以走，以及当前单元格所在的行和列。所以如果只是简单的设计成二维数组是不可以的，因此，我们可以定义一个MazeNode类,东南西北四个方向先设为false（即不可走），在后面中做调整。
public class MazeNode {
private int value;
private int xPos;//行下标
private int yPos;//列下标
private boolean way_east
private boolean way_south;
private boolean way_west;
private boolean way_north;
public MazeNode(int value, int xPos, int yPos) {
this.value = value;
this.xPos = xPos;
this.yPos = yPos;
}
}
3）接下来我们设计一个MazeNode类，在MazeNode类中设计一个MazeNode类型的二维数组。然后给二维数组的每个元素赋初值。
public class Maze {
private MazeNode[][] mazeNodes;
private int row;
private int col;
public Maze() {
Scanner scanner = new Scanner(System.in);
System.out.println("请输入迷宫行数：");
this.row = scanner.nextInt();
System.out.println("请输入迷宫列数：");
this.col = scanner.nextInt();
mazeNodes = new MazeNode[row][col];
}
private void initValue() { //从键盘输入row行，col列数据，初始化二维数组
Scanner scanner = new Scanner(System.in);
System.out.println("请设置迷宫 0 or 1");
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
this.mazeNodes[i][j] = new MazeNode(scanner.nextInt(), i, j);
}
}
}
}
4）假定初始化了一个3×3的二维数组，里面的值如下
现在每个元素的东南西北四个方向都是false，我们要调整每个0元素东南西北四个方向的布尔值，如果该0元素的东南西北任何一个方向是0的话，表示是空地，可以通过，把这个方向的布尔值设为true，表示可以通过。
private void adjustState() { //调整当前节点的东 南 西 北 四个方向的状态 如果为 0 改为true
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (mazeNodes[i][j].getValue() == 1) {
continue;
}
//mazeNodes[i][j] == 0;// 0 2 row = 2 col = 3
if ((j + 1 < col) && mazeNodes[i][j + 1].getValue() == 0) {//东
mazeNodes[i][j].setWay_east(true);
}
if ((i + 1 < row) && mazeNodes[i + 1][j].getValue() == 0) {//南
mazeNodes[i][j].setWay_south(true);
}
if ((j - 1 >= 0) && mazeNodes[i][j - 1].getValue() == 0) {//西
mazeNodes[i][j].setWay_west(true);
}
if ((i - 1 >= 0) && mazeNodes[i - 1][j].getValue() == 0) {//北
mazeNodes[i][j].setWay_north(true);
}
}
}
}
调整好每个0元素四个方向的布尔值后，要开始走迷宫啦，从左上角开始入迷宫，当然如果左上角第一个元素为1的话就肯定进不去迷宫了，也就走迷宫失败了。当遇到0就开始通过，走的过程中我们要注意，走过来了就不要走老路了，就不要回去了，一直向前，不后退，这就要把当前走到的位置的相反方向设为false，防止回去,比如你往东走到了新的位置，就要把当前位置的西边设为false，这样就不会回去了。如果在走的过程中，发现无路可走了，就要退一步开始寻求新路，这时候就要注意了，当我们退一步后，上一次的路就不能走了，就要把上次走的方向设为false，防止走老路。可是我们已经把回去的路封住了，那么应该怎么退回去呢？
在这里我们可以运用栈的特点来 *** 作。
栈有一个特点就是先进后出，后进先出,我们可以把栈想象成一个瓶子，先进的肯定要后出，后进的肯定要先出了。如图：
在图示中，进栈的顺序是4 0 2 1，出栈的顺序就是1 0 2 4。同时还要了解出栈 *** 作pop（），入栈 *** 作push（），获得栈顶元素peek（）。
因此我们可以利用栈的特性来走迷宫，每到达一个位置，把该位置元素入栈；退一步，进行栈顶元素出栈 *** 作，直到栈中元素为空退出循环，不再进行，也就是不存在有效迷宫路径，否则到达右下角元素位置，走迷宫成功。（在maze类中添加实例变量private Stack stack;;构造函数中添加stack = new Stack<>();因为 *** 作的数组是MazeNode类型，在这里用到泛型。）
代码如下：
public void goMaze() {
initValue();//初始化迷宫 -->从键盘输入
adjustState();//调整当前节点四个方向的行走状态
//判断左上角和右下角是否为 0 不为 0 则不能
if (mazeNodes[0][0].getValue() == 1 || mazeNodes[row - 1][col - 1].getValue() == 1) {
System.out.println("不存在有效路径");
return;
}
stack.push(mazeNodes[0][0]);//左上角节点入栈
while (stack.isEmpty() == false) {
MazeNode top = stack.peek();//获取栈顶元素
int x_Pos = top.getxPos();//获取当前节点的x坐标
int y_Pos = top.getyPos();//获取当前节点的y坐标
//如果当前节点正好是迷宫右下角节点，那么走出迷宫成功
if (x_Pos == row - 1 && y_Pos == col - 1) {
System.out.println("走出迷宫成功");
break;
}
if (top.isWay_east()) {//东
stack.push(mazeNodes[x_Pos][y_Pos + 1]);//把当前节点的东边节点压入栈
mazeNodes[x_Pos][y_Pos + 1].setWay_west(false);//防止节点往回走
mazeNodes[x_Pos][y_Pos].setWay_south(false);//防止节点走老路
} else if (top.isWay_south()) {//南
stack.push(mazeNodes[x_Pos + 1][y_Pos]);
mazeNodes[x_Pos + 1][y_Pos].setWay_north(false);
mazeNodes[x_Pos][y_Pos].setWay_south(false);
} else if (top.isWay_west()) {//西
stack.push(mazeNodes[x_Pos][y_Pos - 1]);
mazeNodes[x_Pos][y_Pos - 1].setWay_east(false);
mazeNodes[x_Pos][y_Pos].setWay_west(false);
} else if (top.isWay_north()) {//北
stack.push(mazeNodes[x_Pos - 1][y_Pos]);
mazeNodes[x_Pos - 1][y_Pos].setWay_south(false);
mazeNodes[x_Pos][y_Pos].setWay_south(false);
} else {//无路可走
stack.pop();
}
}
show();
}
4）打印函数，如果栈中为空，表示没有迷宫路径；栈不为空，就要把走的迷宫路径标识出来，可以把走过的位置值置为2。获得栈顶元素，把该元素所在值置为2，然后出栈，再获得栈顶元素，把元素的所在值置为2，然后出栈…直到栈为空。遍历二维数组，打印数组。
private void show() {
if (stack.isEmpty()) {
System.out.print("没有迷宫路径");
return;
}
while (!stack.isEmpty()) {
MazeNode top = stack.peek();
top.setValue(2);
stack.pop();
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
System.out.print(mazeNodes[i][j].getValue() + " ");
}
System.out.println();
}
}
5.迷宫完整代码
MazeNode类：
package com.wysheng.迷宫;
public class MazeNode {
private int value;
private int xPos;//行下标
private int yPos;//列下标
private boolean way_east;
private boolean way_south;
private boolean way_west;
private boolean way_north;
public MazeNode(int value, int xPos, int yPos) {
this.value = value;
this.xPos = xPos;
this.yPos = yPos;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public void setWay_east(boolean way_east) {
this.way_east = way_east;
}
public void setWay_south(boolean way_south)
{
this.way_south = way_south;
}
public void setWay_west(boolean way_west) {
this.way_west = way_west;
}
public void setWay_north(boolean way_north) {
this.way_north = way_north;
}
public boolean isWay_east() {
return way_east;
}
public boolean isWay_south() {
return way_south;
}
public boolean isWay_west() {
return way_west;
}
public boolean isWay_north() {
return way_north;
}
public int getxPos() {
return xPos;
}
public int getyPos() {
return yPos;
}
}
Maze类：
package com.wysheng.迷宫;
import java.util.Scanner;
import java.util.Stack;
public class Maze {
private MazeNode[][] mazeNodes;
private int row;
private int col;
private Stack stack;
public Maze() {
stack = new Stack<>();
Scanner scanner = new Scanner(System.in);
System.out.println("请输入迷宫行数：");
this.row = scanner.nextInt();
System.out.println("请输入迷宫列数：");
this.col = scanner.nextInt();
mazeNodes = new MazeNode[row][col];
}
private void initValue() { //从键盘输入row行，col列数据，初始化二维数组
Scanner scanner = new Scanner(System.in);
System.out.println("请设置迷宫 0 or 1");
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
this.mazeNodes[i][j] = new MazeNode(scanner.nextInt(), i, j);
}
}
}
//打印迷宫
private void show() {
if (stack.isEmpty()) {
System.out.print("没有迷宫路径");
return;
}
while (!stack.isEmpty()) {
MazeNode top = stack.peek();
top.setValue(2);
stack.pop();
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
System.out.print(mazeNodes[i][j].getValue() + " ");
}
System.out.println();
}
}
private void adjustState() { //调整当前节点的东 南 西 北 四个方向的状态 如果为 0 改为true
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (mazeNodes[i][j].getValue() == 1) {
continue;
}
//mazeNodes[i][j] == 0;// 0 2 row = 2 col = 3
if ((j + 1 < col) && mazeNodes[i][j + 1].getValue() == 0) {//东
mazeNodes[i][j].setWay_east(true);
}
if ((i + 1 < row) && mazeNodes[i + 1][j].getValue() == 0) {//南
mazeNodes[i][j].setWay_south(true);
}
if ((j - 1 >= 0) && mazeNodes[i][j - 1].getValue() == 0) {//西
mazeNodes[i][j].setWay_west(true);
}
if ((i - 1 >= 0) && mazeNodes[i - 1][j].getValue() == 0) {//北
mazeNodes[i][j].setWay_north(true);
}
}
}
}
public void goMaze() {
initValue();//初始化迷宫 -->从键盘输入
adjustState();//调整当前节点四个方向的行走状态
//判断左上角和右下角是否为 0 不为 0 则不能
if (mazeNodes[0][0].getValue() == 1 || mazeNodes[row - 1][col - 1].getValue() == 1) {
System.out.println("当前迷宫不可走");
return;
}
stack.push(mazeNodes[0][0]);//左上角节点入栈
while (stack.isEmpty() == false) {
MazeNode top = stack.peek();//获取栈顶元素
int x_Pos = top.getxPos();//获取当前节点的x坐标
int y_Pos = top.getyPos();//获取当前节点的y坐标
//如果当前节点正好是迷宫右下角节点，那么走出迷宫成功
if (x_Pos == row - 1 && y_Pos == col - 1) {
System.out.println("不存在有效路径");
break;
}
if (top.isWay_east()) {//东
stack.push(mazeNodes[x_Pos][y_Pos + 1]);//把当前节点的东边节点压入栈
mazeNodes[x_Pos][y_Pos + 1].setWay_west(false);//防止节点往回走
mazeNodes[x_Pos][y_Pos].setWay_south(false);//防止节点走老路
} else if (top.isWay_south()) {//南
stack.push(mazeNodes[x_Pos + 1][y_Pos]);
mazeNodes[x_Pos + 1][y_Pos].setWay_north(false);
mazeNodes[x_Pos][y_Pos].setWay_south(false);
} else if (top.isWay_west()) {//西
stack.push(mazeNodes[x_Pos][y_Pos - 1]);
mazeNodes[x_Pos][y_Pos - 1].setWay_east(false);
mazeNodes[x_Pos][y_Pos].setWay_west(false);
} else if (top.isWay_north()) {//北
stack.push(mazeNodes[x_Pos - 1][y_Pos]);
mazeNodes[x_Pos - 1][y_Pos].setWay_south(false);
mazeNodes[x_Pos][y_Pos].setWay_south(false);
} else {//无路可走
stack.pop();
}
}
show();
}
}
MazeTest类：
package com.wysheng.迷宫;
public class MazeTest {
public static void main(String[] args) {
Maze maze = new Maze();
maze.goMaze();
}
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）