12–递归【迷宫问题】

 1 //递归 --> 迷宫问题

 2 public class MazeQuestion {
 3 
 4     public static void main(String[] args) {
 5         //二维数组
 6         int[][] migong = new int[8][7];
 7         //用 1 来表示墙壁
 8         //先将上下左右作用初始化为1
 9         for (int i = 0; i < 8; i++) {
10             for(int j = 0; j < 7; j++) {
11                 migong[0][j] = 1; //上
12                 migong[7][j] = 1; //下
13                 migong[i][0] = 1; //左
14                 migong[i][6] = 1; //右
15             }
16         }
17         //设置障碍
18         migong[3][1] = 1;
19         migong[3][2] = 1;
20         System.out.println("输出地图 --> ");
21         showMap(migong);
22         
23         setWay(migong, 1, 1);
24         
25         System.out.println("路径图：");
26         showMap(migong);
27     }
28     
29     public static void showMap(int[][] migong) {
30         for(int i = 0; i < 8; i++) {
31             for(int j = 0; j < 7; j++) {
32                 System.out.print(migong[i][j] + " ");
33             }
34             System.out.println();
35         }
36     }
37     
38     //从migong[1][1] --> migong[6][5];
39     //设置路径
40     //1：表示墙壁、 2：表示通路   3：表示此路不通
41     /**
42      * @param migong 要走的地图
43      * @param i 从第(i+1)行开始走
44      * @param j 从第(j+1)列开始
45      * 按照下右上左的顺序走
46      */
47     public static boolean setWay(int[][] migong, int i, int j) {
48         if (migong[6][5] == 2) {
49             return true;
50         }else {
51             if (migong[i][j] == 0) {
52                 migong[i][j] = 2;
53                 if (setWay(migong, i+1, j)) { //下
54                     return true;
55                 }else if(setWay(migong, i, j+1)){ //右
56                     return true;
57                 }else if (setWay(migong, i-1, j)) { //上
58                     return true;
59                 }else if(setWay(migong, i, j-1)) { //左
60                     return true;
61                 }else {     //说明该点是死路,即没有到达终点的路径
62                     migong[i][j] = 3;
63                     return false;
64                 }
65             }else {
66                 return false;
67             }
68         }    
69     }
70 
71 }