当前位置:主页 > java教程 > 使用栈的迷宫算法java版代码

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

发布:2019-09-16 20:57:25 184


本站收集了一篇相关的编程文章,网友冀和豫根据主题投稿了本篇教程内容,涉及到java、迷宫算法、使用栈的迷宫算法java版代码相关内容,已被499网友关注,下面的电子资料对本篇知识点有更加详尽的解释。

使用栈的迷宫算法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调用ChatGPT的实现代码

    发布:2023-03-29

    这篇文章主要介绍了Java调用ChatGPT的实现代码,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下


  • Java ArrayList扩容机制原理深入分析

    发布:2023-03-26

    在Java中,ArrayList是最常用的集合之一。它是一种容器,它的内部定义了一个Object类型的数组elementData,因此可用于存储任意类型的数据。我们知道,数组是长度恒定的。而ArrayList相当于是一个长度可变的动态数组,一起来看看的它的扩容机制


  • Java 实现简单静态资源Web服务器的示例

    发布:2022-09-12

    给大家整理一篇关于Java的教程,这篇文章主要介绍了Java 实现简单静态资源Web服务器的示例,帮助大家更好的理解和使用Java,感兴趣的朋友可以了解下


  • java导出Excel的实例功能详解

    发布:2019-08-07

    这篇文章主要为大家详细介绍了java实现导出Excel的功能,具有一定的参考价值,感兴趣的小伙伴们可以参考一下


  • JavaScript转换数据库DateTime字段类型的实例详解

    发布:2020-01-07

    下面小编就为大家带来一篇JavaScript转换数据库DateTime字段类型方法。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧


  • 通过Java实现添加或删除PDF中的附件

    发布:2023-04-19

    当我们在制作PDF文件或者PPT演示文稿的时候,为了让自己的文件更全面详细,就会在文件中添加附件。本文为大家整理了Java实现添加或删除PDF中的附件的方法,需要的可以参考下


  • 详解Java如何实现百万数据excel导出功能

    发布:2023-04-16

    这篇文章主要为大家详细介绍了Java如何实现百万数据excel导出功能,文中的示例代码讲解详细,具有一定的借鉴价值,需要的可以参考一下


  • Java集合教程之Collection实例详解

    Java集合教程之Collection实例详解

    发布:2022-06-15

    给网友们整理关于Collection的教程,集合,或者叫容器,是一个包含多个元素的对象,下面这篇文章主要给大家介绍了关于Java集合教程之Collection的相关资料,文中通过示例代码介绍的非常详细,需要的朋友可以参考下


网友讨论