使用栈的迷宫算法java版代码
作者:young_leez 发布时间:2022-03-07 12:47:16
标签:java,迷宫算法
本文为大家分享了使用栈的迷宫算法java版,主要考察栈的使用,供大家参考,具体内容如下
主要思路如下:
do {
if(当前位置可通过) {
标记此位置已走过;
保存当前位置并入栈;
if(当前位置为终点) {
程序结束;
}
获取下一个位置;
}
else {
if(栈非空) {
出栈;
while(当前位置方向为4且栈非空) {
标记当前位置不可走;
出栈;
}
if(当前位置的方向小于4) {
方向+1;
重新入栈;
获取下一个位置;
}
}
}
}
while (栈非空);
java代码如下:
import java.util.Stack;
public class Maze {
// 栈
private Stack<MazeNode> stack = new Stack<Maze.MazeNode>();
// 迷宫
private int[][] maze = {
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{1,0,1,0,0,0,1,1,0,0,0,1,1,1,1,1,1},
{1,0,0,0,0,1,1,0,1,1,1,0,0,1,1,1,1},
{1,0,1,1,0,0,0,0,1,1,1,1,0,0,1,1,1},
{1,1,1,0,0,1,1,1,1,1,1,0,1,1,0,0,1},
{1,1,0,0,1,0,0,1,0,1,1,1,1,1,1,1,1},
{1,0,0,1,1,1,1,1,1,0,1,0,0,1,0,1,1},
{1,0,0,1,1,1,1,1,1,0,1,0,0,1,0,1,1},
{1,0,1,1,1,0,0,0,0,1,1,1,1,1,1,1,1},
{1,0,0,1,1,0,1,1,0,1,1,1,1,1,0,1,1},
{1,1,0,0,0,0,1,1,0,1,0,0,0,0,0,0,1},
{1,1,0,1,1,1,1,1,0,0,0,1,1,1,1,0,1},
{1,0,0,0,0,1,1,1,1,1,0,1,1,1,1,0,1},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
};
// 标记路径是否已走过
private int[][] mark = new int[MAZE_SIZE_X][MAZE_SIZE_Y];
private static final int MAZE_SIZE_X = 14;
private static final int MAZE_SIZE_Y = 17;
private static final int END_X = 12;
private static final int END_Y = 15;
private void initMark() {
for (int i = 0; i < MAZE_SIZE_X; i++) {
for (int j = 0; j < MAZE_SIZE_Y; j++) {
mark[i][j] = 0;
}
}
}
public void process() {
initMark();
Position curPos = new Position(1, 1);
do {
// 此路径可走
if (maze[curPos.x][curPos.y] == 0 && mark[curPos.x][curPos.y] == 0) {
mark[curPos.x][curPos.y] = 1;
stack.push(new MazeNode(curPos, 1));
// 已到终点
if (curPos.x == END_X && curPos.y == END_Y) {
return;
}
curPos = nextPos(curPos, stack.peek().direction);
}
// 走不通
else {
if (!stack.isEmpty()) {
MazeNode curNode = stack.pop();
while (curNode.direction == 4 && !stack.isEmpty()) {
// 如果当前位置的4个方向都已试过,那么标记该位置不可走,并出栈
mark[curNode.position.x][curNode.position.y] = 1;
curNode = stack.pop();
}
if (curNode.direction < 4) {
curNode.direction++;// 方向+1
stack.push(curNode);// 重新入栈
curPos = nextPos(curNode.position, curNode.direction);// 获取下一个位置
}
}
}
}
while(!stack.isEmpty());
}
public void drawMaze() {
for (int i = 0; i < maze.length; i++) {
for (int j = 0; j < maze[0].length; j++) {
System.out.print(maze[i][j]);
}
System.out.print("\n");
}
System.out.print("\n");
}
public void drawResult() {
initMark();
MazeNode node;
while (!stack.isEmpty()) {
node = stack.pop();
mark[node.position.x][node.position.y] = 1;
}
for (int i = 0; i < mark.length; i++) {
for (int j = 0; j < mark[0].length; j++) {
System.out.print(mark[i][j]);
}
System.out.print("\n");
}
System.out.print("\n");
}
// 记录迷宫中的点的位置
class Position {
int x;
int y;
public Position(int x, int y) {
this.x = x;
this.y = y;
}
}
// 栈中的结点
class MazeNode {
Position position;
int direction;
public MazeNode(Position pos) {
this.position = pos;
}
public MazeNode(Position pos, int dir) {
this.position = pos;
this.direction = dir;
}
}
// 下一个位置,从右开始,顺时针
public Position nextPos(Position position, int direction) {
Position newPosition = new Position(position.x, position.y);
switch (direction) {
case 1:
newPosition.y += 1;
break;
case 2:
newPosition.x += 1;
break;
case 3:
newPosition.y -= 1;
break;
case 4:
newPosition.x -= 1;
break;
default:
break;
}
return newPosition;
}
public static void main(String[] args) {
Maze maze = new Maze();
maze.drawMaze();
maze.process();
maze.drawResult();
}
}
来源:http://blog.csdn.net/Young_Leez/article/details/44026295
0
投稿
猜你喜欢
- 本文实例为大家分享了java生成验证码图片的具体代码,供大家参考,具体内容如下示例一:import org.apache.commons.c
- 正在尝试分配更低的访问权限?在进行Java编程时会给我们报出如下提示怎么办?这里我们将给大家介绍详细的解决方法。首先,查看,控制台给出的提示
- 一、文件存储特点:openFileInput()和openFileOutput()读取设备上的文件。优点:适用于存储大量的数据,可以存储图片
- Mybatis Plus select 查询部分字段Mybatis Plus select语句默认查询所有字段,如需要指定字段查询,则需使用
- 文件目录结构文件目录结构很重要,特别注意的是rule文件要放在主启动类上一级位置,才能够扫描。写pom<dependencies>
- 1.<constant name="struts.i18n.encoding" value="UTF-8
- 在logback.xml中加上该配置,包名如:com.xxx<logger name="packageName"
- 需求在配置类中,从application.properties中读取一个复杂list。如List<Person>或者初始化一个m
- 前言我们在日常开发中,经常会用到一个系统需要链接多个数据库来实现业务的需求,比如多个系统之间数据调用、两个数据之间同步等等。今天给大家分享使
- Java环境部署下载所需软件和依赖安装 jdk路径可选别的盘。但是指向时得注意我自己时装在 F 盘的,在f盘里新建文件夹 Java,Java
- 前言在我们平时使用图形化界面的时候,会发现来建立一个文件夹或者一个文档的时候很简单,只需要在桌面单击鼠标右键就可以了。但是,在我们写项目的时
- 要想使Java运行,我们可以设计一个面向Java语言特性的虚拟机,并通过编译器将Java程序转换为它可以识别的指令序列,也称为Java字节码
- 初学C++的朋友经常在类中看到public,protected,private以及它们在继承中表示的一些访问范围,很容易搞糊涂。今天本文就来
- 1. 在原有工程目录右键-> new ->Module->:2. 选择library:3. 一路next,最后finish
- <%@ page language="java" contentType="text/html; cha
- 题目:使用栈计算类似表达式:5+2*3-2 的计算结果 提示:简易计算器操作符号限于+,-,*,/的计算分析思路:1、
- 本文实例讲述了java继承中的构造方法。分享给大家供大家参考。具体如下:继承中的构造方法: 1、子类的构造过程中必须调用其基类的构造方法。2
- makeCertPic.javapackage pic;import java.awt.Color;import java.awt.Font
- 概述在一个程序执行的过程中,各条语句的执行顺序对程序的结果是有直接影响的。也就是说,程序的流程对运行结果有直接的影响。所以,我们必须清楚每条
- 前2天有读者问到是否有带分页功能的表格控件,今天分页功能的表格控件详细解析。PaginatedDataTablePaginatedDataT