使用棧的迷宮算法java版代碼

更新時間：2020年05月27日 09:30:25 作者：young_leez

這篇文章主要為大家詳細介紹了使用棧的迷宮算法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();
 }

}

以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章:

Springboot集成ProtoBuf的實例
這篇文章主要介紹了Springboot集成ProtoBuf的實例，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
2022-03-03
java HttpClient傳輸json格式的參數(shù)實例講解
這篇文章主要介紹了java HttpClient傳輸json格式的參數(shù)實例講解，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧
2021-01-01
Zookeeper的選舉機制詳解
Zookeeper的選舉機制是基于ZAB協(xié)議的Paxos變種,通過LOOKING、PROPOSAL、ACCEPT和COMMIT四個階段,確保集群中只有一個領導節(jié)點,選舉過程中,服務器通過投票和收集投票信息,確定ZXID和SID來選擇領導者,FastLeaderElection算法優(yōu)化了選舉過程,提高選舉效率
2025-02-02
SpringBoot中RabbitMQ集群的搭建詳解
單個的?RabbitMQ?肯定無法實現(xiàn)高可用，要想高可用，還得上集群。這篇文章主要介紹了SpringBoot中RabbitMQ集群的兩種模式的搭建：普通集群搭建和鏡像集群搭建，需要的朋友可以參考一下
2021-12-12
java集合迭代器Iterator中的remove陷阱
這篇文章主要介紹了java集合迭代器Iterator中的remove陷阱,需要的朋友可以參考下
2016-04-04
Java中的訪問修飾符詳細解析
以下是對Java中的訪問修飾符進行了詳細的分析介紹，需要的朋友可以過來參考下
2013-09-09
SpringBoot中GlobalExceptionHandler異常處理機制詳細說明
Spring Boot的GlobalExceptionHandler是一個全局異常處理器,用于捕獲和處理應用程序中發(fā)生的所有異常,這篇文章主要給大家介紹了關于Java中GlobalExceptionHandler異常處理機制的相關資料,需要的朋友可以參考下
2024-03-03
Java 線程的優(yōu)先級(setPriority)案例詳解
這篇文章主要介紹了Java 線程的優(yōu)先級(setPriority)案例詳解,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下
2021-08-08
Spring Boot 中的Servlet簡單使用
在spring boot中添加自己的Servlet有兩種方法，代碼注冊Servlet和注解自動注冊（Filter和Listener也是如此）。這篇文章主要介紹了Spring Boot 中的Servlet簡單使用,需要的朋友可以參考下
2017-04-04
Spring boot 路徑映射的實現(xiàn)
這篇文章主要介紹了spring boot 路徑映射的實現(xiàn),文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
2019-11-11