利用Java解決走迷宮問題
概述
假設有一個如下圖所示的迷宮，灰色部分是墻壁不可走，白色部分是可以走的路，藍色位置為迷宮的入口，綠色位置為出口，從入口出發，規定只能通過向上、向下、向左和向右方向進行走動，問如何才能找到一條到達出口的通路，
思路
-
可以用一個二維矩陣來模擬迷宮地圖，0代表灰色部分的墻壁，1代表白色部分可走的路
-
當每走過一個位置后，把改位置的值標記為-1，如果該位置標記為-1，則不可以重復走
-
判斷當前位置是否有路可走，根據向右、向下、向左、向上的順序判斷該位置的下一步是否有路可走
-
每走一步，需要把每一步的位置坐標保存起來，記錄走過的位置
-
當走到死胡同，沒路可走時，回溯到前面的位置，并判斷該位置是否有路可走
-
如果有路可走，則繼續往下走，反之則繼續回退到前面一個位置繼續查找，直到找到有路可走為止
實作程序
建立迷宮地圖
public class walkMaze {
private static int[][] maze = //建立迷宮地圖，0代表可走的路，1代表墻壁不可走
{{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}};
private static ArrayList<Point> route = new ArrayList<>(); //走迷宮的路線
//列印輸出迷宮地圖
public static void main(String[] args) {
for (int i = 0; i < maze.length; i++) {
for (int j = 0; j < maze.length; j++) {
System.out.print(maze[i][j]+" ");
}
System.out.println();
}
}
}
判斷往右下左上方向是否可以走
private static boolean isWalk(int[][] maze,Point currentPoint){
int x = currentPoint.x;
int y = currentPoint.y;
//往右走
if (maze[y][x+1]!=1 && maze[y][x+1]!=-1){
route.add(new Point(x+1,y));
return true;
}
//往下走
if (maze[y+1][x]!=1 && maze[y+1][x]!=-1){
route.add(new Point(x,y+1));
return true;
}
//往左走
if (maze[y][x-1]!=1 && maze[y][x-1]!=-1){
route.add(new Point(x-1,y));
return true;
}
//往上走
if (maze[y-1][x]!=1 && maze[y-1][x]!=-1){
route.add(new Point(x,y-1));
return true;
}
return false;
}
走迷宮核心代碼
private static boolean maze(int[][] maze,Point enter){
//標記入口位置，并將入口位置加入串列中
maze[enter.y][enter.x]=-1;
route.add(enter);
//判斷串列是否為空
while (!route.isEmpty()){
while (isWalk(maze,enter)){
//串列中的最后一個元素
enter = route.get(route.size()-1);
//判斷改位置是否是出口位置
if (enter.x==8 && enter.y==8){
return true;
}else{
//標記已走過的位置
maze[enter.y][enter.x]=-1;
}
}
//當走到死胡同的時候，回溯到前面的位置，并判斷改位置是否有路可走
// 如果有路可走，則繼續往下走，反之則繼續回退到前面一個位置繼續查找，直到找到有路可走為止
//將串列最后一個元素去除，并取出去除后最后的元素
route.remove(route.size()-1);
enter = route.get(route.size()-1);
}
return false;
}
測驗輸出走迷宮路線
public static void main(String[] args) {
//走迷宮
boolean flag = maze(walkMaze.maze, new Point(1, 1));
if (flag){
System.out.println("成功找到迷宮的出口！\n路線如下：");
for (int i = 0; i < route.size(); i++) {
System.out.print("("+route.get(i).x+","+route.get(i).y+")");
if (i!=route.size()-1){
System.out.print("->");
}
}
}
}
結果顯示
這樣就順利找到了迷宮的出口了，按照代碼運行輸出的路線坐標去根據迷宮地圖去走，最終就可以到達迷宮的出口，順利走出迷宮，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/237535.html
標籤：其他
上一篇：仿Pi模式的 Bee Network 挖礦游戲安裝指導（限Apple）
下一篇：原生JS實作貪吃蛇游戲