快捷導(dǎo)航

java 實現(xiàn)迷宮回溯算法示例詳解

更新時間：2020年07月31日 09:53:57 作者：Lzfa

這篇文章主要介紹了java 實現(xiàn)迷宮回溯算法示例詳解，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

用一個7 x 7的矩形表示迷宮，0和1分別表示的是通路和障礙。通過設(shè)計編寫程序找到藍(lán)色小球達(dá)到藍(lán)色旗子的路線

在這里插入圖片描述

思路：

構(gòu)建一個迷宮（用二維數(shù)組）實現(xiàn)找通路的方法findRoad()
構(gòu)建二維數(shù)組不難，我們主要是要實現(xiàn)findRoad()這個方法，在實現(xiàn)這個方法前，我們需要約定好一下幾個點：小球的位置當(dāng)作入口（1，1），小旗的位置當(dāng)作出口（5，5）數(shù)組里數(shù)的含義分別為(0沒有走過)、(1障礙)、(2走過且為正確的路線)、(3走過且為錯誤的路線)將我們每一步的走法稱為策略：下 -> 右 -> 上 ->左

實現(xiàn)

首先構(gòu)建出迷宮

public static void main(String[] args) {
  //1.創(chuàng)建二維數(shù)組模擬迷宮
  int[][] maze = new int[7][7];
  //2.初始化迷宮
  for (int i = 0; i < maze.length; i++) {
   //maze[i][j]:i控制行 j:控制列
   maze[0][i] = 1;//第1行都為1
   maze[6][i] = 1;//最后一行都為1
   maze[i][0] = 1;//第一列都為1
   maze[i][6] = 1;//最后一列都為1
   //其他位置的1
   maze[4][1] = 1;
   maze[4][2] = 1;
   maze[4][3] = 1;
   maze[4][4] = 1;
   maze[3][4] = 1;
   maze[2][3] = 1;
  }
  //打印迷宮
  System.out.println("完成迷宮初始化：");
  for (int i = 0; i < maze.length; i++) {
   for (int j = 0; j < maze[i].length; j++) {
    System.out.print(maze[i][j] + " ");
   }
   System.out.println();
  }
 }

然后寫findRoad()方法

  * 使用遞歸回溯找通路 （5，5為出口）
  * @param maze 迷宮
  * @param i 從哪個位置開始找
  * @param j 從哪個位置開始找
  * @return 找到通路返回true 否則false
  */
 public static boolean findRoad(int[][] maze, int i, int j) {
  //策略：下 -> 右 -> 上 ->左
  //0：沒有走過 1：障礙 2:走過且為正確的路線 3：走過且為錯誤的路線
  if (maze[5][5] == 2) {//找到通路
   return true;
  } else {
   if (maze[i][j] == 0) {
    //當(dāng)前點沒走過，按策略走
    maze[i][j] = 2;//當(dāng)前點改為2，假定能走通
    if (findRoad(maze, i + 1, j)) {//向下走
     return true;
    } else if (findRoad(maze, i, j + 1)) {//向右走
     return true;
    } else if (findRoad(maze, i - 1, j)) {//向上走
     return true;
    } else if (findRoad(maze, i, j - 1)) {//向左走
     return true;
    } else {
     //該點無法走通
     maze[i][j] = 3;
     return false;//返回到上個方法（即返回到上個點）
    }
   } else {
    //該點為 1或2或3，無法走通，直接返回上個方法（即上個點）
    return false;
   }
  }
 }

main方法調(diào)用findRoad()方法，傳入創(chuàng)建好的迷宮，和入口點（1，1）

//mian方法中調(diào)用findRoad()方法
  findRoad(maze,1,1);
  //打印迷宮
  System.out.println("完成路線的迷宮：");
  for (int i = 0; i < maze.length; i++) {
   for (int j = 0; j < maze[i].length; j++) {
    System.out.print(maze[i][j] + " ");
   }
   System.out.println();
  }

效果

在這里插入圖片描述