java尋找迷宮路徑的簡單實(shí)現(xiàn)示例
迷宮項(xiàng)目實(shí)現(xiàn)設(shè)計文檔
項(xiàng)目介紹:
一個網(wǎng)格迷宮由n行m列的單元格組成,每個大院個要么是空地(用0表示),要么是障礙物(用1表示)。你的任務(wù)是找一條從起點(diǎn)到終點(diǎn)的移動序列,其中只能上下左右移動到相鄰單元格。任何時候都不能在有障礙物的單元格中,也不能走到迷宮之外。起點(diǎn)為左上角和終點(diǎn)右下角。
項(xiàng)目功能:
解決迷宮路徑查找問題,尋找一條從左上角迷宮入口到右下角迷宮出口的一條有效路徑,0代表可走,1代表不能行走,找到請輸出最終的迷宮和路徑信息,找不到請輸出不存在有效路徑。
項(xiàng)目所用知識點(diǎn):
采用Java面向?qū)ο笏枷?,二維數(shù)組以及非遞歸棧進(jìn)行實(shí)現(xiàn)
項(xiàng)目實(shí)現(xiàn)思路:
1.定義一個迷宮節(jié)點(diǎn)類型(MazeNode)的二維數(shù)組
2.初始化每個格子中的value值。給二維數(shù)組每個格子存放對象。對象的value值只能為0(當(dāng)前格子可以走)或者1(當(dāng)前格子不能走)
3.創(chuàng)建圍墻,可以有效防止越界問題。根據(jù)當(dāng)前節(jié)點(diǎn)周圍四個方向格子中的value值,判斷當(dāng)前節(jié)點(diǎn)的上下左右四個方向是否可走(0是可走,1不可走)。
4.開始走迷宮。采用棧操作,記錄行走的路徑,將元素入棧,判斷當(dāng)前棧頂元素的哪個方向可走,將其中一個可走方向進(jìn)行入棧操作,直到右下角元素停止。棧中保存走過的路徑。 注意: 如果遇到走入死胡同問題,此時需要將是棧頂元素并且棧頂元素的四個方向都不能行走,此時將其出棧,選擇新方向再次入棧,直到右下角元素停止。
項(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)建一個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){//判斷終點(diǎn)是否正確 System.out.println("迷宮終點(diǎn)錯誤"); } 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 } //改變找個點(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)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
如何在spring boot中進(jìn)行參數(shù)校驗(yàn)示例詳解
這篇文章主要介紹了如何在spring-boot中進(jìn)行參數(shù)校驗(yàn)及l(fā)ombok的使用詳解,本文通過實(shí)例代碼給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-05-05Java final static abstract關(guān)鍵字概述
這篇文章主要介紹了Java final static abstract關(guān)鍵字的相關(guān)資料,需要的朋友可以參考下2016-05-05springBoot集成mybatis 轉(zhuǎn)換為 mybatis-plus方式
這篇文章主要介紹了springBoot集成mybatis 轉(zhuǎn)換為 mybatis-plus方式,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2021-12-12java實(shí)現(xiàn)多線程交替打印兩個數(shù)
這篇文章主要為大家詳細(xì)介紹了java實(shí)現(xiàn)多線程交替打印兩個數(shù),文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下2020-11-11基于JVM 調(diào)優(yōu)的技巧總結(jié)分析
本篇文章是對JVM 調(diào)優(yōu)的技巧進(jìn)行了總結(jié)和分析。需要的朋友參考下2013-05-05Spring Boot項(xiàng)目中定制攔截器的方法詳解
這篇文章主要介紹了Spring Boot項(xiàng)目中定制攔截器的方法詳解,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-10-10