黑马程序员技术交流社区

标题: 一道迷宫的算法问题（递归） [打印本页]

---

作者: 金辉    时间: 2013-6-20 01:15
标题: 一道迷宫的算法问题（递归）

1. public class Maze {
   
2.         public static int judge(int[][] arr,int i,int j,int[] a){
   
3.                 int[] b=new int[2];//记录走过的路
   
4.                 if(arr[i][j]==1){//判断如果是墙的话，返回0
   
5.                         return 0;
   
6.                 }
   
7.                 if(i==5&&j==5){//判断如果到出口返回1
   
8.                         return 1;
   
9.                 }
   
10.                 //分别判断上下左右四个方向的情况，如果有墙的话，就走不通。
    
11.                 //他所走过的时候如果前面有路，是不会往回走的
    
12.                 if(!(arr[i-1][j]==1||(i-1==a[0]&&j==a[1]))){//判断向上走的情况
    
13.                         b[0]=i;
    
14.                         b[1]=j;
    
15.                         if(judge(arr,i-1,j,b)==1)
    
16.                                 return 1;
    
17.                 }
    
18.                 if(!(arr[i][j+1]==1||(i==a[0]&&j+1==a[1]))){//就判断向右走的情况
    
19.                         b[0]=i;
    
20.                         b[1]=j;
    
21.                         if(judge(arr,i,j+1,b)==1)
    
22.                                 return 1;
    
23.                 }
    
24.                 if(!(arr[i+1][j]==1||(i+1==a[0]&&j==a[1]))){//判断向下走的情况
    
25.                         b[0]=i;
    
26.                         b[1]=j;
    
27.                         if(judge(arr,i+1,j,b)==1)
    
28.                                 return 1;
    
29.                 }
    
30.                 if(!(arr[i][j-1]==1||(i==a[0]&&j-1==a[1]))){//判断向左走的情况
    
31.                         b[0]=i;
    
32.                         b[1]=j;
    
33.                         if(judge(arr,i-1,j,b)==1)
    
34.                                 return 1;
    
35.                 }
    
36.                 return 0;
    
37.         }
    
38.         public static void main(String[] args) {   
    
39.                 int[][] arr = { { 1, 1, 1, 1, 1, 1, 1 }, //把迷宫用二维数组表示
    
40.                                         { 1, 0, 1, 0, 0, 0, 1 },
    
41.                                         { 1, 0, 1, 0, 1, 1, 1 },
    
42.                                         { 1, 0, 0, 0, 1, 0, 1 },
    
43.                                         { 1, 0, 1, 0, 0, 0, 1 },
    
44.                                         { 1, 0, 1, 0, 1, 0, 1 },
    
45.                                         { 1, 1, 1, 1, 1, 1, 1 } };
    
46.                 int[] a={0,1};//记录走过的前一格坐标。第一格的前一格假定为0,1
    
47.                 System.out.println(judge(arr,1,1,a));//从1,1开始
    
48.         }
    
49. }
    

复制代码

题目是用递归得出迷宫从入口到出口的路径，是原图那样的，不过那样的话要判断数组越界问题，就人为加了一圈墙。墙用1表示，可以走的用0表示，现在是递归到出口后怎么解决记录路径的问题，可能前面的代码也不一定对，大家帮忙看下

1.JPG (15.47 KB, 下载次数: 0)

下载附件

2013-6-20 01:10 上传

原图

DC894EF8-C8FA-48B8-88B3-DDB329CE4301.jpg (19.9 KB, 下载次数: 0)

下载附件

2013-6-20 01:11 上传

改过的

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2