迷宫的小问题，大家帮忙看一下，加大米

就是找到所有可以从起点到终点的路径，我搜了一下代码：

1. package org.stack;
   
2. 
   
3. public class Maze {
   
4.         private static int startI,startJ;//入口坐标
   
5.         private static int endI,endJ;//出口坐标
   
6.        
   
7.         public void start(int startI,int startJ){
   
8.                 this.startI=startI;
   
9.                 this.startJ=startJ;
   
10.         }
    
11.         public void end(int endI,int endJ){
    
12.                 this.endI=endI;
    
13.                 this.endJ=endJ;
    
14.         }
    
15. 
    
16.         public static void main(String[] args) {
    
17.                  int maze[][] ={{2, 2, 2, 2, 2, 2, 2, 2, 2},   
    
18.                                         {2, 0, 0, 0, 0, 0, 0, 0, 2},   
    
19.                                         {2, 0, 2, 2, 0, 2, 2, 0, 2},   
    
20.                                         {2, 0, 2, 0, 0, 2, 0, 0, 2},   
    
21.                                         {2, 0, 2, 0, 2, 0, 2, 0, 2},   
    
22.                                         {2, 0, 0, 0, 0, 0, 2, 0, 2},   
    
23.                                         {2, 2, 0, 2, 2, 0, 2, 2, 2},   
    
24.                                         {2, 0, 0, 0, 0, 0, 0, 0, 2},   
    
25.                                         {2, 2, 2, 2, 2, 2, 2, 2, 2}};   
    
26.                
    
27.                 create(maze);
    
28. 
    
29.                 Maze cell=new Maze();
    
30.                 cell.start(1, 1);
    
31.                 cell.end(7, 7);
    
32.                
    
33.                 visited(maze, startI, startJ);
    
34.         }
    
35.        
    
36.         public static void visited(int[][] cell,int i,int j){
    
37.                 cell[i][j]=1;
    
38.                 if(i==endI&&j==endJ){
    
39.                         System.out.println("走完一条路线");
    
40.                         for(int m=0;m<cell.length;m++){
    
41.                                 for(int n=0;n<cell[0].length;n++){
    
42.                                         if(cell[m][n]==2){
    
43.                                                 System.out.print("#");
    
44.                                         }else if (cell[m][n]==1) {
    
45.                                                 System.out.print("*");
    
46.                                         }else {
    
47.                                                 System.out.print(" ");
    
48.                                         }
    
49.                                 }
    
50.                                 System.out.println();
    
51.                         }
    
52.                 }
    
53.                
    
54.                  //向右
    
55.                 if(cell[i][j+1] == 0){
    
56.                         visited(cell, i, j+1);
    
57.                 }
    
58.                 //向下
    
59.                 if(cell[i+1][j] == 0){
    
60.                         visited(cell, i+1, j);
    
61.                 }
    
62.                 //向左
    
63.                 if(cell[i][j-1] == 0){
    
64.                         visited(cell, i, j-1);
    
65.                 }
    
66.                 //向上
    
67.                 if(cell[i-1][j] == 0){
    
68.                         visited(cell, i-1, j);
    
69.                 }
    
70.                
    
71.                 cell[i][j]=0;
    
72.         }
    
73.        
    
74.        
    
75.         //打印迷宫图
    
76.         public static void  create(int[][] maze){
    
77.                 for(int i=0;i<maze.length;i++){
    
78.                         for(int k=0;k<maze.length;k++){
    
79.                                 if(maze[i][k]==2){
    
80.                                         System.out.print("#");
    
81.                                 }else {
    
82.                                         System.out.print(" ");
    
83.                                 }
    
84.                         }
    
85.                         System.out.println();
    
86.                 }
    
87.         }
    
88. }

复制代码

路径张贴之后就不好看了，大家可以再eclipse里运行一下，Here is my Q：
第一次遍历数组到了点A[5,7],再往下就不是0了，接下来改怎么运行呢？我感觉卡住了

1. 
   

复制代码

- = ..leetcode unique path ii

看了一遍代码，好像没什么错，不知道楼主遇到了什么问题？

itbwtw 发表于 2014-7-2 19:54
看了一遍代码，好像没什么错，不知道楼主遇到了什么问题？

他没有标记走过的路径吧???

readman 发表于 2014-7-2 21:05
他没有标记走过的路径吧???

他用2表示墙壁，用0表示道路，已经走过的用1来表示
在递归函数里，他先用cell(i,j)=1;表示这个点走过了，然后向下搜索，搜完四个方向以后，再cell(i,j)=0;也就是复原。
也许复原这步有点难理解：
他先标记，然后搜索，所以在搜索下一层的时候这一层是标记为1的，如果搜到了最后一层（i==endI&&j==endJ），就把整张图打印，那么其中之前的所有1就能形成通路，如果不是最后一层，就继续向下搜（这一层仍然为1）。最后，如果向四个方向搜索完了，再把这一层标记为0，表示没有走过，这样才不会对上一层产生影响。

p.s.建议在网上找几篇深搜的教程看一看，理解一下什么是深搜。
如果不明白的话，先做这个题：给你N个数，输出这N个数的全排列。
比如给你1 2 3，你就输出1 2 3，1 3 2,2 1 3,2 3 1,3 1 2，3 2 1
如果全排列的问题搞懂了，这个走迷宫的问题也就明白了。
再不明白的话，找一本数据结构的书，看一下图的深度优先遍历，也可以明白。

itbwtw 发表于 2014-7-2 22:39
他用2表示墙壁，用0表示道路，已经走过的用1来表示
在递归函数里，他先用cell(i,j)=1;表示这个点走过了 ...

ArrayList<ArrayList<Integer>> result = new  ArrayList<ArrayList<Integer>>();
Arrays.sort(num)
boolean[] visited = new boolean[num.length];
public void rec (int[] num, boolean[] visited, ArrayList<Integer> temp) {
if (temp.size() == num.length)
   result.add(temp);
   return;
}
for(int i = 0 ; i < num.length; i++) {
  if (visited == false) {
    visited  = true;
    temp.add(num);
    rec(num, visited, temp);    visited = false;
    temp.remove(temp.size() - 1);
}
}

- = 大概是这样

readman 发表于 2014-7-2 23:19
ArrayList result = new  ArrayList();
Arrays.sort(num)
boolean[] visited = new boolean[num.lengt ...

我看应该没问题，你运行一下看结果对就行了。
这个弄懂的话，那个迷宫应该就没问题了吧？

补充内容 (2014-7-3 13:39):
我看错了，我还以为你是楼主。。。。

itbwtw 发表于 2014-7-2 22:39
他用2表示墙壁，用0表示道路，已经走过的用1来表示
在递归函数里，他先用cell(i,j)=1;表示这个点走过了 ...

谢谢你的解答！我的问题是第一次递归遍历Maze数组到了点[5,7],再往下就不是0了，接下来改怎么运行呢？这个时候[5,7]就不制成1，而是执行第71行，之后到哪一行呢？

itbwtw 发表于 2014-7-2 22:39
他用2表示墙壁，用0表示道路，已经走过的用1来表示
在递归函数里，他先用cell(i,j)=1;表示这个点走过了 ...

另外从Maze的第一个点开始就算一直向右遍历吧？右边的点满足为0也轮不到后面的if啊，只有到右边界的时候在向下搜索吧

itbwtw 发表于 2014-7-2 22:39
他用2表示墙壁，用0表示道路，已经走过的用1来表示
在递归函数里，他先用cell(i,j)=1;表示这个点走过了 ...

搜完第一个点后就一直在if(cell[j+1] == 0)里递归啊，根本轮不到向下

readman 发表于 2014-7-2 17:49
- = ..leetcode unique path ii

搜完第一个点后就一直在if(cell[j+1] == 0)里递归啊，根本轮不到向下

readman 发表于 2014-7-2 23:19
ArrayList result = new  ArrayList();
Arrays.sort(num)
boolean[] visited = new boolean[num.lengt ...

你这样编译Ok吗？

数字媒体技术 发表于 2014-7-4 10:32
你这样编译Ok吗？

嗯? 什么ok么?
我就是写个模版

TonyJang 发表于 2014-7-4 09:43
另外从Maze的第一个点开始就算一直向右遍历吧？右边的点满足为0也轮不到后面的if啊，只有到右边界的时候 ...

我明白你的意思了（虽然我还不知道你的（5,7）是怎么来的）。
你有这个问题的话我还是推荐你看一下我最开始回复的帖子。
下面关于你的这个问题：
抽象的来讲，你的问题是，一个函数在执行完了以后（即执行return ;了以后），程序接下来怎么运行。这个问题很简单，当然回到调用这个函数的地方，运行下一行。只不过递归有一点让人迷惑。
你可以用树来帮助你理解，这个程序向4个方向搜索，所以是一个四叉树（当然实际上不是这样，对墙壁和已经访问过的点不搜索）。调用一次递归函数就是开启一个子树（向右搜），子树搜完以后回到这里，开下一个子树（向下搜），再向左搜，再向上搜，搜完四个方向以后回到上一层，这对于上一层来说相当于搜完了一个方向，上一层会开启下一个方向，那下一个方向又开四个方向。。。。直到visit（1,1）这个函数所开的四个方向（实际上它只开了2个）全部return，整个图遍历结束

所以我引用的你说的这段话是错的，递归不是像你说的这样运作的，你说的是遍历一种线性数据结构，递归是像网一样运作的，它面向的非线性的数据结构（图）。

TonyJang 发表于 2014-7-4 09:46
搜完第一个点后就一直在if(cell[j+1] == 0)里递归啊，根本轮不到向下

说具体一点，这个递归是这样运作的：
向右搜到头，然后向下搜到头，然后向左搜到头，然后向上搜到头，全都到头了（死路），就往回走一个，然后接着搜下一个方向（你刚才4次搜到头对于往回走的这一层来说只搜完了一个方向，比如是搜完了右）然后下，左，上搜到头，然后又死路了，再往回走一个，然后向下一个方向。。。。
这种撞了南墙然后往回走一个的搜法就是所谓的深度优先遍历。。。。。