一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 475|回复: 15
收起左侧

[算法题] 迷宫的小问题,大家帮忙看一下,加大米

[复制链接] |试试Instant~ |关注本帖
TonyJang 发表于 2014-7-2 17:13:19 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 TonyJang 于 2014-7-2 17:14 编辑

就是找到所有可以从起点到终点的路径,我搜了一下代码:
  1. package org.stack;

  2. public class Maze {
  3.         private static int startI,startJ;//入口坐标
  4.         private static int endI,endJ;//出口坐标
  5.        
  6.         public void start(int startI,int startJ){
  7.                 this.startI=startI;
  8.                 this.startJ=startJ;
  9.         }
  10.         public void end(int endI,int endJ){
  11.                 this.endI=endI;
  12.                 this.endJ=endJ;
  13.         }

  14.         public static void main(String[] args) {
  15.                  int maze[][] ={{2, 2, 2, 2, 2, 2, 2, 2, 2},   
  16.                                         {2, 0, 0, 0, 0, 0, 0, 0, 2},   
  17.                                         {2, 0, 2, 2, 0, 2, 2, 0, 2},   
  18.                                         {2, 0, 2, 0, 0, 2, 0, 0, 2},   
  19.                                         {2, 0, 2, 0, 2, 0, 2, 0, 2},   
  20.                                         {2, 0, 0, 0, 0, 0, 2, 0, 2},   
  21.                                         {2, 2, 0, 2, 2, 0, 2, 2, 2},   
  22.                                         {2, 0, 0, 0, 0, 0, 0, 0, 2},   
  23.                                         {2, 2, 2, 2, 2, 2, 2, 2, 2}};   
  24.                
  25.                 create(maze);

  26.                 Maze cell=new Maze();
  27.                 cell.start(1, 1);
  28.                 cell.end(7, 7);
  29.                
  30.                 visited(maze, startI, startJ);
  31.         }
  32.        
  33.         public static void visited(int[][] cell,int i,int j){
  34.                 cell[i][j]=1;
  35.                 if(i==endI&&j==endJ){
  36.                         System.out.println("走完一条路线");
  37.                         for(int m=0;m<cell.length;m++){
  38.                                 for(int n=0;n<cell[0].length;n++){
  39.                                         if(cell[m][n]==2){
  40.                                                 System.out.print("#");
  41.                                         }else if (cell[m][n]==1) {
  42.                                                 System.out.print("*");
  43.                                         }else {
  44.                                                 System.out.print(" ");
  45.                                         }
  46.                                 }
  47.                                 System.out.println();
  48.                         }
  49.                 }
  50.                
  51.                  //向右
  52.                 if(cell[i][j+1] == 0){
  53.                         visited(cell, i, j+1);
  54.                 }
  55.                 //向下
  56.                 if(cell[i+1][j] == 0){
  57.                         visited(cell, i+1, j);
  58.                 }
  59.                 //向左
  60.                 if(cell[i][j-1] == 0){
  61.                         visited(cell, i, j-1);
  62.                 }
  63.                 //向上
  64.                 if(cell[i-1][j] == 0){
  65.                         visited(cell, i-1, j);
  66.                 }
  67.                
  68.                 cell[i][j]=0;
  69.         }
  70.        
  71.        
  72.         //打印迷宫图
  73.         public static void  create(int[][] maze){
  74.                 for(int i=0;i<maze.length;i++){
  75.                         for(int k=0;k<maze.length;k++){
  76.                                 if(maze[i][k]==2){
  77.                                         System.out.print("#");
  78.                                 }else {
  79.                                         System.out.print(" ");
  80.                                 }
  81.                         }
  82.                         System.out.println();
  83.                 }
  84.         }
  85. }
复制代码
路径张贴之后就不好看了,大家可以再eclipse里运行一下,Here is my Q:
第一次遍历数组到了点A[5,7],再往下就不是0了,接下来改怎么运行呢?我感觉卡住了





readman 发表于 2014-7-2 17:49:18 | 显示全部楼层
- = ..leetcode unique path ii
回复 支持 反对

使用道具 举报

itbwtw 发表于 2014-7-2 19:54:43 | 显示全部楼层
看了一遍代码,好像没什么错,不知道楼主遇到了什么问题?
回复 支持 反对

使用道具 举报

readman 发表于 2014-7-2 21:05:22 | 显示全部楼层
itbwtw 发表于 2014-7-2 19:54
看了一遍代码,好像没什么错,不知道楼主遇到了什么问题?

他没有标记走过的路径吧???
回复 支持 反对

使用道具 举报

itbwtw 发表于 2014-7-2 22:39:26 | 显示全部楼层
本帖最后由 itbwtw 于 2014-7-2 22:42 编辑
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
如果全排列的问题搞懂了,这个走迷宫的问题也就明白了。
再不明白的话,找一本数据结构的书,看一下图的深度优先遍历,也可以明白。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

readman 发表于 2014-7-2 23:19:42 | 显示全部楼层
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);
}
}


- = 大概是这样

回复 支持 反对

使用道具 举报

itbwtw 发表于 2014-7-2 23:37:39 | 显示全部楼层
readman 发表于 2014-7-2 23:19
ArrayList result = new  ArrayList();
Arrays.sort(num)
boolean[] visited = new boolean[num.lengt ...

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

补充内容 (2014-7-3 13:39):
我看错了,我还以为你是楼主。。。。
回复 支持 反对

使用道具 举报

 楼主| TonyJang 发表于 2014-7-4 09:17:59 | 显示全部楼层
itbwtw 发表于 2014-7-2 22:39
他用2表示墙壁,用0表示道路,已经走过的用1来表示
在递归函数里,他先用cell(i,j)=1;表示这个点走过了 ...

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

使用道具 举报

 楼主| TonyJang 发表于 2014-7-4 09:43:04 | 显示全部楼层
itbwtw 发表于 2014-7-2 22:39
他用2表示墙壁,用0表示道路,已经走过的用1来表示
在递归函数里,他先用cell(i,j)=1;表示这个点走过了 ...

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

使用道具 举报

 楼主| TonyJang 发表于 2014-7-4 09:46:22 | 显示全部楼层
itbwtw 发表于 2014-7-2 22:39
他用2表示墙壁,用0表示道路,已经走过的用1来表示
在递归函数里,他先用cell(i,j)=1;表示这个点走过了 ...

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

使用道具 举报

 楼主| TonyJang 发表于 2014-7-4 09:46:29 | 显示全部楼层
readman 发表于 2014-7-2 17:49
- = ..leetcode unique path ii

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

使用道具 举报

数字媒体技术 发表于 2014-7-4 10:32:33 | 显示全部楼层
本帖最后由 数字媒体技术 于 2014-7-4 10:33 编辑
readman 发表于 2014-7-2 23:19
ArrayList result = new  ArrayList();
Arrays.sort(num)
boolean[] visited = new boolean[num.lengt ...
你这样编译Ok吗?
回复 支持 反对

使用道具 举报

readman 发表于 2014-7-4 12:42:55 | 显示全部楼层

嗯? 什么ok么?
我就是写个模版
回复 支持 反对

使用道具 举报

itbwtw 发表于 2014-7-5 11:42:33 | 显示全部楼层
TonyJang 发表于 2014-7-4 09:43
另外从Maze的第一个点开始就算一直向右遍历吧?右边的点满足为0也轮不到后面的if啊,只有到右边界的时候 ...

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

所以我引用的你说的这段话是错的,递归不是像你说的这样运作的,你说的是遍历一种线性数据结构,递归是像网一样运作的,它面向的非线性的数据结构(图)。
回复 支持 反对

使用道具 举报

itbwtw 发表于 2014-7-5 11:52:39 | 显示全部楼层
TonyJang 发表于 2014-7-4 09:46
搜完第一个点后就一直在if(cell[j+1] == 0)里递归啊,根本轮不到向下

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

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 18:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表