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

項(xiàng)目介紹：

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

項(xiàng)目功能：

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

項(xiàng)目所用知識點(diǎn)：

采用Java面向?qū)ο笏枷耄S數(shù)組以及非遞歸棧進(jìn)行實(shí)現(xiàn)

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

項(xiàng)目實(shí)現(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)建一個(gè)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('迷宮入口路徑錯(cuò)誤'); } if(mazenode[row-2][colum-2].value!=0){//判斷終點(diǎn)是否正確 System.out.println('迷宮終點(diǎn)錯(cuò)誤'); } for(int i=1,j=1;;){//起點(diǎn) i=route.gettop().index1;//賦值棧頂元素的下標(biāo)一給i j=route.gettop().index2;//賦值棧頂元素的下標(biāo)二給j if(i==row-2&&j==colum-2){break; }//抵達(dá)終點(diǎn)退出循環(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++){//進(jìn)行打印 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;//下標(biāo)1 this.index2=index2;//下標(biāo)2 } //改變找個(gè)點(diǎn)的值為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尋找迷宮路徑的簡單實(shí)現(xiàn)示例的文章就介紹到這了,更多相關(guān)java 尋找迷宮路徑內(nèi)容請搜索好吧啦網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持好吧啦網(wǎng)！