溫馨提示×
您好，登錄后才能下訂單哦！
點(diǎn)擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
這期內(nèi)容當(dāng)中小編將會(huì)給大家?guī)碛嘘P(guān)使用java實(shí)現(xiàn)尋找迷宮路徑，文章內(nèi)容豐富且以專業(yè)的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。
項(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)目所用知識(shí)點(diǎn)：
采用Java面向?qū)ο笏枷?，二維數(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;
}
}
}上述就是小編為大家分享的使用java實(shí)現(xiàn)尋找迷宮路徑了，如果剛好有類似的疑惑，不妨參照上述分析進(jìn)行理解。如果想知道更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號(hào)
手機(jī)網(wǎng)站二維碼