java 用递归实现迷宫算法

话不多说，上代码：

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
import java.util.Scanner;    
public class Main  
{  
    static int length,wideth;//迷宫矩阵的长度和宽度  
    static int x,y;//起始位置的坐标  
    static String[][] arr;//迷宫的二维数组  
    static int n;//当前走的走的步数，初始值设置为10000意为无穷  
	private static Scanner in;
    public static void main(String[] args){  
    	in = new Scanner (System.in);
    	System.out.println("输入迷宫的长度、宽度(行数和列数不超过50）");
    	wideth =in.nextInt();
    	length =in.nextInt();  //让用户输入迷宫的宽度和长度
    	arr = new String[wideth][length];
    	System.out.println("请输入"+wideth+"行"+length+"列的迷宫 ('0'表示墙，'1' 表示道路 '4'表示起点 '5'表示终点 )");
//从键盘读取迷宫
    	for (int i=0;i<wideth;i++) {
			for(int j=0;j<length;j++) {
				arr[i][j] = in.next();
		      }
			   }
//遍历一次迷宫，找到起点，记下起点的坐标    
    	for (int i=0;i<wideth;i++) {
			for(int j=0;j<length;j++) {	
				if (arr[i][j].equals("4")) {
					x=i;
					y=j;
                }
		     }
		}
//开始尝试找出口
try {	
		Running(x,y,n);
		
}catch (Exception e) {
//接收异常，打印数组
	     System.out.println();
	     System.out.println("找到出口！路径如下(*代表路径)：");
	     for (int i=0;i<wideth;i++) {	
			for(int j=0;j<length;j++) {	
				System.out.print(arr[i][j]);
					if(j==length-1) 
						 System.out.println();
					else System.out.print(" ");
					}
		      }
	     
            System.exit(0); //结束程序
        }
//如果程序正常退出，说明迷宫没有出口
         System.out.println("该迷宫没有出口！！！");
		
    }
    
/*找出口的递归函数*/
 public static void Running(int x,int y,int n){  
     
//	 System.out.println(x+" "+y+" "+n);//打印每一步方便理解
	 
 
 		if(arr[x][y].equals("5")||n==10000){ 
            int i = 1/0; //当找到出口'5'时，抛出异常，跳出整个递归函数   
        } 
 		if(!arr[x][y].equals("4")) //若非起点和终点，将该点做个记号"*"表示已经走过
 			arr[x][y]="*";
 		  
/*判断上下左右有没有终点*/
        if(y-1>=0&&arr[x][y-1].equals("5")){  
            Running(x,y-1,n+1);  
        }  
        if(x-1>=0&&arr[x-1][y].equals("5")){  
            Running(x-1,y,n+1);  
        }  
        if(y+1<length&&arr[x][y+1].equals("5")){  
            Running(x,y+1,n+1);  
        }  
        if(x+1<wideth&&arr[x+1][y].equals("5")){  
            Running(x+1,y,n+1);  
        }
       
/*如果没有终点，则看上下左右有没有道路*/  
        if(x+1<wideth&&arr[x+1][y].equals("1")){  
            Running(x+1,y,n+1);  //向下
        } 
        if(y+1<length&&arr[x][y+1].equals("1")){  
            Running(x,y+1,n+1);  //向右
        } 
        if(y-1>=0&&(arr[x][y-1].equals("1"))){  
            Running(x,y-1,n+1);  //向左
        }  
        if(x-1>=0&&arr[x-1][y].equals("1")){  
            Running(x-1,y,n+1);  //向上
        }   

         arr[x][y]="#"; //如果没有道路,说明是死胡同，将改点标记为“#”
/* 再看上下左右有没有之前走过的路并返回之前走过的路*/
         if(y-1>=0&&(arr[x][y-1].equals("*"))){  
             Running(x,y-1,n+1);  
         }  
         if(x-1>=0&&arr[x-1][y].equals("*")){  
             Running(x-1,y,n+1);  
         }  
         if(y+1<length&&arr[x][y+1].equals("*")){  
             Running(x,y+1,n+1);  
         }  
         if(x+1<wideth&&arr[x+1][y].equals("*")){  
             Running(x+1,y,n+1);  
         }  
 /*     如果上诉条件都不满足，说明该方向的道路是死路，该层递归结束，返回上一层递归 
       以此类推，直到返回第一层递归，继续找其他方向的路。
       在第一层递归中，如果上述条件都不满足，说明迷宫没有出口
       程序正常退出，不会抛出异常
 */
         }
   
}

运行效果图：