时间:2021-05-19
本文为大家分享了使用栈的迷宫算法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(); }}以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
C++自定义栈实现迷宫求解一:迷宫求解是一个锻炼我们的算法求解能力的问题,它的实现方法有很多;今天我们就介绍其中的用栈求解的方法。二:什么是栈:大家应该都有往袋
本文实例讲述了C语言使用深度优先搜索算法解决迷宫问题。分享给大家供大家参考,具体如下:深度优先搜索伪代码(Pseudocode)如下:将起点标记为已走过并压栈;
数据结构实验课要求解决一个迷宫问题,这里给定长宽用prime算法随机生成了一个迷宫并从指定起点与终点打印出了迷宫的解决方案,此处用到了栈数据结构,这里的jmc:
最近经常在机房看同学在玩一个走迷宫的游戏,比较有趣,自己也用java写一个实现随机生成迷宫的算法,其实就是一个图的深度优先遍历算法.基本思想就是,迷宫中的每个点
本文实例为大家分享了C++实现迷宫游戏的具体代码,供大家参考,具体内容如下运用并查集自动生成迷宫地图,并运用队列和栈寻找迷宫通路并打印出来#include#in