題目描述

代碼實現

package com.atguigu.recursion;/*** @創建人 wdl* @創建時間 2021/3/21* @描述*/ public class MiGong {public static void main(String[] args) {//先創建一個二維數組，模擬迷宮//地圖int[][] map = new int[8][7];//使用1表示墻//上下全部置為1for (int i = 0; i < 7; i++) {map[0][i]=1;map[7][i]=1;}//左右全部置為1for (int i = 0; i < 8; i++) {map[i][0]=1;map[i][6]=1;}//設置擋板，1表示map[3][1]=1;map[3][2]=1; // map[1][2]=1;map[2][2]=1;//輸出地圖System.out.println("地圖的情況");for (int i = 0; i < 8; i++) {for (int j = 0; j < 7; j++) {System.out.print(map[i][j]+" ");}System.out.println();}//使用遞歸回溯給小球找路(引用類型)setWay(map,1,1);//輸出新的地圖，小球走過，并標識過的地圖System.out.println("小球走過，并標識過的地圖情況");for (int i = 0; i < 8; i++) {for (int j = 0; j < 7; j++) {System.out.print(map[i][j]+" ");}System.out.println();}}//使用遞歸回溯來給小球找路//說明//1.map表示地圖//2.i，j表示從地圖哪個位置開始找（1,1）//3.如果小球能到map[6][5]位置，則說明通路找到//4.約定，當map[i][j]為0表示沒有走過，當為1表示墻；2表示通路可以走 3.表示該點已經走過，但是走不通//5.在走迷宮時，需要確定一個策略(方法)下->右->上->左，如果該點走不通，再回溯/**** @param map 表示地圖* @param i 從哪個位置開始找* @param j* @return 如果找到通路，就返回true，否則返回false*///使用遞歸回溯給小球找路public static boolean setWay(int [][]map,int i,int j){if(map[6][5]==2){//通路已經找到OKreturn true;}else {if(map[i][j]==0){//如果當前這個點還沒有走過//策略(方法)下->右->上->左走map[i][j]=2;//假定該點是可以走通if (setWay(map,i+1,j)){//向下走return true;}else if(setWay(map,i,j+1)){//向右走return true;}else if (setWay(map,i-1,j)){//向上走return true;}else if(setWay(map,i,j-1)){//向左走return true;}else {//說明該點是走不通的，是死路map[i][j]=3;return false;}}else {//如果map[i][j]!=0,可能是1,2,3return false;}}}}

總結

以上是生活随笔為你收集整理的迷宫问题---递归解决的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。