递归实现迷宫找路径

蔚落 2022-09-08 03:56 214阅读 0赞

package com.example.datastructrue.reback;
    
    public class MiGong {
        
        public static void main(String[] args) {
        
    
    //        设置一个二维数组当做地图
            int[][] map = new int[8][7];
    
    //        值为0的是没走过的路
            for (int i=0;i<8;i++){
        
                for (int j = 0 ;j<7;j++){
        
                    map[i][j] = 0;
                }
            }
    
    //        值为1的是墙
            for (int i=0;i<7;i++){
        
                map[0][i] = 1;
                map[7][i] = 1;
            }
    //        值为1的是墙
            for (int i =0;i<7;i++){
        
                map[i][0]=1;
                map[i][6]=1;
            }
    
    //        值为1的是墙
            map[3][1]=1;
            map[3][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();
            }
    
            System.out.println("走过后的地图");
            MiGong.setWay(map,1,1);
            for (int i=0;i<8;i++){
        
                for (int j = 0;j<7;j++){
        
                    System.out.print(map[i][j]+" ");
                }
                System.out.println();
            }
    
        }
    //    创建一个方法，来标记能够走通迷宫的路线。参数为二维数组，以及从哪个地点开始出发
        public static boolean setWay(int[][] map,int i,int j){
        
    //        判断终点是否已经被标记为2了，如果是，说明路通了
            if(map[6][5]==2){
        
                return true;
            }else {
        
    //            判断地点是否能够行走
                if(map[i][j]==0){
        
    //                将该地点标记为2，2说明该地点是能够通行的
                    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;
                    }
    //                如果下、右、上、左都不能通行则将该地点设置为3
                    else {
        
                        map[i][j]=3;
                        return false;
                    }
                }
                else{
        
                    return false;
                }
            }
        }
    
    }