快捷導(dǎo)航

java尋找迷宮路徑的簡單實現(xiàn)示例

更新時間：2020年10月26日 12:00:10 作者：tdongmu

這篇文章主要介紹了java尋找迷宮路徑的簡單實現(xiàn)示例，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習或者工作具有一定的參考學(xué)習價值，需要的朋友們下面隨著小編來一起學(xué)習學(xué)習吧

迷宮項目實現(xiàn)設(shè)計文檔

項目介紹：

一個網(wǎng)格迷宮由n行m列的單元格組成，每個大院個要么是空地（用0表示），要么是障礙物（用1表示）。你的任務(wù)是找一條從起點到終點的移動序列，其中只能上下左右移動到相鄰單元格。任何時候都不能在有障礙物的單元格中，也不能走到迷宮之外。起點為左上角和終點右下角。

項目功能：

解決迷宮路徑查找問題，尋找一條從左上角迷宮入口到右下角迷宮出口的一條有效路徑，0代表可走，1代表不能行走，找到請輸出最終的迷宮和路徑信息，找不到請輸出不存在有效路徑。

項目所用知識點：

采用Java面向?qū)ο笏枷?，二維數(shù)組以及非遞歸棧進行實現(xiàn)

項目實現(xiàn)思路：
1.定義一個迷宮節(jié)點類型（MazeNode）的二維數(shù)組
2.初始化每個格子中的value值。給二維數(shù)組每個格子存放對象。對象的value值只能為0（當前格子可以走）或者1（當前格子不能走）
3.創(chuàng)建圍墻，可以有效防止越界問題。根據(jù)當前節(jié)點周圍四個方向格子中的value值，判斷當前節(jié)點的上下左右四個方向是否可走（0是可走，1不可走）。
4.開始走迷宮。采用棧操作，記錄行走的路徑，將元素入棧，判斷當前棧頂元素的哪個方向可走，將其中一個可走方向進行入棧操作，直到右下角元素停止。棧中保存走過的路徑。注意: 如果遇到走入死胡同問題，此時需要將是棧頂元素并且棧頂元素的四個方向都不能行走，此時將其出棧，選擇新方向再次入棧，直到右下角元素停止。

項目實現(xiàn) ：

Maze類

import java.util.Scanner;

public class Maze {
  private MazeNode[][] mazenode;
  private int row ;//行
  private int colum;//列
  public Maze(){


  }
  public void innode(){//添加迷宮路徑；
    Scanner scanner=new Scanner(System.in);
    System.out.println("請輸入迷宮行數(shù)和列數(shù)");
    row=scanner.nextInt()+2;//為后面加圍墻
    colum=scanner.nextInt()+2;
    System.out.println("請輸入迷宮路徑：");
    mazenode=new MazeNode[row][colum];
    build(mazenode);//創(chuàng)建一個row行colum列的mazenode并且把value值都給1
    for(int i=1;i<row-1;i++){//為圍墻內(nèi)value賦值；
      for(int j=1;j<colum-1;j++){
      mazenode[i][j].value=scanner.nextInt();

  }
    }
  }
//創(chuàng)建圍墻；
  public void build(MazeNode[][] mazenode){
    for(int i=0;i<row;i++){
      for(int j=0;j<colum;j++){
        mazenode[i][j]=new MazeNode(1,i,j);
      }
    }
  }
  public void goMaze(){//走迷宮
    innode();
    MyStack route=new MyStack();//存放路徑的盞
    if(mazenode[1][1].value==0){//判斷入口是否可走；
    route.push(mazenode[1][1]);
    }else {System.out.println("迷宮入口路徑錯誤");
    }
    if(mazenode[row-2][colum-2].value!=0){//判斷終點是否正確
      System.out.println("迷宮終點錯誤");
    }
    for(int i=1,j=1;;){//起點
      i=route.gettop().index1;//賦值棧頂元素的下標一給i
      j=route.gettop().index2;//賦值棧頂元素的下標二給j
      if(i==row-2&&j==colum-2){
        break;
      }//抵達終點退出循環(huán)
        if(mazenode[i][j].right(mazenode,i,j+1)){//判斷右邊是否可走
          if(route.contain(route,mazenode,i,j+1)){//判斷右邊是否在棧內(nèi)
            mazenode[i][j].changeValue(mazenode,i,j);
            route.pop(mazenode[i][j]);//如果存在退棧
          }else {
          route.push(mazenode[i][j+1]);//如果不存在入棧的右邊
          }
        } else if(i+1<row&&mazenode[i][j].down(mazenode,i+1,j)){
          if(route.contain(route,mazenode,i+1,j)){//判斷下邊是否在棧內(nèi)
            mazenode[i][j].changeValue(mazenode,i,j);
            route.pop(mazenode[i+1][j]);退棧
          }else {
          route.push(mazenode[i+1][j]);
          }
        }else if(i+1<row&&mazenode[i][j].left(mazenode,i,j-1)){
          if(route.contain(route,mazenode,i,j-1)){//判斷左邊是否在棧內(nèi)
            mazenode[i][j].changeValue(mazenode,i,j);
            route.pop(mazenode[i][j]);退棧
          }else{
          route.push(mazenode[i][j-1]);
          }
        }else if(i+1<row&&mazenode[i][j].up(mazenode,i-1,j)){
          if(route.contain(route,mazenode,i-1,j)){//判斷上邊是否在棧內(nèi)
            mazenode[i][j].changeValue(mazenode,i,j);
            route.pop(mazenode[i][j]);退棧
          }else{
          route.push(mazenode[i-1][j]);
          }
        }
    }
    route.toRoute();//修改路徑的值
    for(int i=1;i<row-1;i++){//進行打印
      for(int j=1;j<colum-1;j++){
        System.out.print(mazenode[i][j].value+" ");
      }
      System.out.println();
    }
  }
}

mazenode類

public class MazeNode {
  public int index1;
  public int index2;
  public int value;
  public MazeNode(int value,int index1,int index2) {
    this.value=value;
    this.index1=index1;//下標1
    this.index2=index2;//下標2
  }
  //改變找個點的值為2
  public void changeValue(MazeNode[][] mazeNode,int index1,int index2){

    mazeNode[index1][index2].value=2;
  }
  //判斷左邊是否可走
  public boolean left(MazeNode[][] mazeNode,int index1,int index2){
    if(mazeNode[index1][index2].value==0){
    return true;
    }return false;
  }
  //判斷上邊是否可走
  public boolean up(MazeNode[][] mazeNode,int index1,int index2){
    if(mazeNode[index1][index2].value==0){
      return true;
    }return false;
  }
  //判斷右邊是否可走
  public boolean right(MazeNode[][] mazeNode,int index1,int index2){
    if(mazeNode[index1][index2].value==0){
      return true;
    }return false;
  }
  //判斷下邊是否可走
  public boolean down(MazeNode[][] mazeNode,int index1,int index2){
    if(mazeNode[index1][index2].value==0){
      return true;
    }return false;
  }
}

MyStake類//棧

import java.util.Arrays;
import java.util.EmptyStackException;

public class MyStack {
  private PuzzleValue[]array2;
  private MazeNode[]array;
  private int size;
  private final int INITSIZE=10;
  public MyStack(){
    array=new MazeNode[INITSIZE];
    array2=new PuzzleValue[INITSIZE];

  }
  //查找棧內(nèi)是否存在此路徑
  public boolean contain(MyStack stack,MazeNode[][] mazeNode,int index1,int index2){

    for(int i=0;i<size;i++){
      if(array[i].index1==index1&&array[i].index2==index2){
        return true;
      }
      }
    return false;
  }
  //入棧
  public void push(MazeNode mazeNode){
    if(array.length==size){
      array= Arrays.copyOf(array,array.length+(array.length>>1));
    }else {
    array[size]=mazeNode;
    size++;
    }
  }
  //出棧
  public void pop(MazeNode mazeNode){
    if(size==0){
      return;
    }else{
      array[size]=null;
      size--;
    }

  }
  //獲得棧頂元素
  public MazeNode gettop(){
    return array[size-1];
  }
  //改變棧內(nèi)的value值
  public void toRoute(){
    for(int i=0;i<size;i++){
      array[i].value=3;
    }
  }
  }

到此這篇關(guān)于java尋找迷宮路徑的簡單實現(xiàn)示例的文章就介紹到這了,更多相關(guān)java 尋找迷宮路徑內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: