java實現find迷宮路徑

迷宮項目實現設計文檔

項目介紹：

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

項目功能：

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

項目所用知識點：

采用Java面向對象思想，二維數組以及非遞歸棧進行實現

項目實現思路：

定義一個迷宮節點類型（MazeNode）的二維數組

初始化每個格子中的value值。給二維數組每個格子存放對象。對象的value值只能為0（當前格子可以走）或者1（當前格子不能走）

創建圍墻，可以有效防止越界問題。根據當前節點周圍四個方向格子中的value值，判斷當前節點的上下左右四個方向是否可走（0是可走，1不可走）。

開始走迷宮。采用棧操作，記錄行走的路徑，將元素入棧，判斷當前棧頂元素的哪個方向可走，將其中一個可走方向進行入棧操作，直到右下角元素停止。棧中保存走過的路徑。 注意: 如果遇到走入死胡同問題，此時需要將是棧頂元素并且棧頂元素的四個方向都不能行走，此時將其出棧，選擇新方向再次入棧，直到右下角元素停止。

項目實現 ：

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("請輸入迷宮行數和列數"); ????????row=scanner.nextInt()+2;//為后面加圍墻 ????????colum=scanner.nextInt()+2; ????????System.out.println("請輸入迷宮路徑："); ????????mazenode=new?MazeNode[row][colum]; ????????build(mazenode);//創建一個row行colum列的mazenode并且把value值都給1 ????????for(int?i=1;i

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]; ????} ????//查找棧內是否存在此路徑 ????public??boolean?contain(MyStack?stack,MazeNode[][]?mazeNode,int?index1,int?index2){ ????????for(int?i=0;i>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]; ????} ????//改變棧內的value值 ????public?void?toRoute(){ ????????for(int?i=0;i

Java

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。