当前位置:首页 > Java技术文章 > 使用栈的迷宫算法java版代码

java使用栈的迷宫算法的实例代码

  • 发布时间:
  • 作者:码农之家原创
  • 点击:184

这篇文章主要知识点是关于java、迷宫算法、的内容,如果大家想对相关知识点有系统深入的学习,可以参阅以下java相关资源

HTML5+CSS3+JavaScript从入门到精通

本书以基础知识、示例、实战案例相结合的方式详尽讲述了HTML,CSS,JavaScript及目前最新的前端技术

查看详情

使用栈的迷宫算法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();
  }

}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持码农之家。

以上就是本次给大家分享的关于Java的全部知识点内容总结,大家还可以在下方相关文章里找到Java文件和base64流相互转换、 Java实现快速排序原理分析、 java图形界面编程的代码详、 等java文章进一步学习,感谢大家的阅读和支持。

上一篇:DispatcherServlet配置的实例方法详解

下一篇:详解SpringMVC的ModelAndView传值方法

展开 +

收起 -

相关内容
疯狂Java讲义

10年经典原创读物,覆盖Java 8、Java 9,第4版保持了前3版系统、全面、讲解浅显、细致的特性,全面新增介绍了Java 9的新特性,从解决问题的角度来介绍Java语言,欢迎下载

查看详情
Java Web从入门到精通

这本书通过通俗易懂的语言、丰富多彩的实例,详细介绍了进行Java Web应用程序开发应该掌握的各方面技术,所有知识都结合具体实例进行介绍,涉及的程序代码给出了详细的注释,可作为初学者的自学用书

查看详情
Java Web开发实例大全:提高卷

本书筛选、汇集了Java Web开发从基础知识到高级应用各个层面,含600经典实例及源码分析,23个应用方向,两卷共1200例,46个方向,供学习、速查、实践练习的超全参考手册

查看详情
Java测试驱动开发

《Java测试驱动开发》最大特点是很薄,看起来没有什么负担。这本书的作用是通过实战让你培养TDD的思路,小编觉得挺不错的,感兴趣的小伙伴们可以参考一下。

查看详情
Java遗传算法编程

本书简单、直接地介绍了遗传算法,并且针对所讨论的示例问题,给出了Java代码的算法实现。全书共分为6章。本书适合机器学习爱好者阅读,尤其适合对遗传算法的理论和实现感兴趣的读者阅

查看详情
你不知道的JavaScript(中卷)

JavaScript这门语言简单易用,很容易上手,但其语言机制复杂微妙,即使是经验丰富的JavaScript开发人员,如果没有认真学习的话也无法真正理解。

查看详情
Java数字图像处理:编程技巧与应用实践

本书首先通过一个简单JAVA图像处理程序勾勒出用JAVA来实现图像处理的基本步骤,介绍JAVA在操作图像方面的几个重要的API类如ImageIO,BufferedImageOP等,并对图像文件的保存与读写做较为深入细致的讲解

查看详情
Java函数式编程

这是一本关于函数式编程的书,由浅入深地介绍了函数式编程的思维方式,非常适合对Java有所了解的程序员,欢迎下载

查看详情
云原生Java

不论是传统式IT制造行业,還是it行业,都正处在制造行业在历史上*强烈的转型中:很多的系统软件已经从传统式的IT构架刹车应用场景云的构架,开发方式也已经从开发设计和运维管理职责分

查看详情
学习笔记
网友NO.485702

Java遗传算法之冲出迷宫

遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。它能解决很多问题,比如数学方程的最大最小值,背包问题,装箱问题等。在游戏开发中遗传算法的应用也十分频繁,不少的游戏 AI都利用遗传算法进行编码。 就个人理解,遗传算法是模拟神奇的大自然中生物“优胜劣汰”原则指导下的进化过程,好的基因有更多的机会得到繁衍,这样一来,随着繁衍的进行,生物种群会朝着一个趋势收敛。而生物繁衍过程中的基因杂交和变异会给种群提供更好的基因序列,这样种群的繁衍趋势将会是“长江后浪推前浪,一代更比一代强”,而不会是只受限于祖先的最好基因。而程序可以通过模拟这种过程来获得问题的最优解(但不一定能得到)。要利用该过程来解决问题,受限……

网友NO.824908

Java实现走迷宫回溯算法

以一个M×N的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。 (1) 根据二维数组,输出迷宫的图形。 (2) 探索迷宫的四个方向:RIGHT为向右,DOWN向下,LEFT向左,UP向上,输出从入口到出口的行走路径。 例子: 左上角(1,1)为入口,右下角(8,9)为出口。 可使用回溯方法,即从入口出发,顺着某一个方向进行探索,若能走通,则继续往前进;否则沿着原路退回,换一个方向继续探索,直至出口位置,求得一条通路。假如所有可能的通路都探索到而未能到达出口,则所设定的迷宫没有通路。 import java.util.*;class Position{ public Position(){ } public Position(int row, int col){ this.col = col; this.row = row; } public String toString(){ return "(" + row + " ," + col + ")"; } int row; int col;}c……

网友NO.408356

Java基于深度优先遍历的随机迷宫生成算法

这两天因为要做一个随机的地图生成系统,所以一直在研究随机迷宫生成算法,好吧,算是有一点小小的成果。 随机迷宫生成我自己的理解简而言之分为以下几步: 1、建立一张地图,我用的二维数组表示,地图上全是障碍物。然后再创建一个用来表示每个格子是否被访问过的二维数组。再创建一个用来表示路径的栈结构。 2、随机选择地图上的一点,呃为了方便我初始点直接取的是左上角即坐标表示为0,0的格子。终点的话因为不涉及到交互就暂时没有。 3、查找当前格子的邻接格(注意,这里的邻接格子都是还未被访问的,下面的代码里有写)。随机选择一个邻接格子为下一格,当前格移动到下一格,标记当前格为已访问,将当前格压入路径栈中。一直重复第三步操作。 4、在第三步操作中,如果当前格子不存在可访问的邻接格,则将栈顶的元素弹……

<
1
>

Copyright 2018-2020 xz577.com 码农之家

本站所有电子书资源不再提供下载地址,只分享来路

免责声明:网站所有作品均由会员网上搜集共同更新,仅供读者预览及学习交流使用,下载后请24小时内删除

版权投诉 / 书籍推广 / 赞助:QQ:520161757