账号密码登录
微信安全登录
微信扫描二维码登录

登录后绑定QQ、微信即可实现信息互通

手机验证码登录
找回密码返回
邮箱找回 手机找回
注册账号返回
其他登录方式
分享
  • 收藏
    X
    【请大牛指教一二】深度优先搜索寻找到达指定位置的路线,想打印出所有路线的时候出错。
    • 2018-07-28 00:00
    • 11
    68
    0

    想要输出所有可能的路线,但是结果只输出一种路线,想了很久没想明白 Orz

    以下是源码:

    //ma是迷宫
    //mb用来标记走过的路mb.fill(0);
    //0表示空地,可通行
    //1表示障碍物,走不动
    //目的地在(x0,y0)
    //position=[]
    //存放的是现在的位置
    //direction=[[-1,0],[0,-1],[1,0],[0,1]];
    //destination=[x0,y0];
     
    let ma = [[0, 0, 1, 0],
              [0, 0, 0, 0],          
              [0, 0, 1, 0],          
              [0, 1, 0, 0],          
              [0, 0, 0, 1]];
     
    let mb = [[1, 0, 0, 0],          
              [0, 0, 0, 0],          
              [0, 0, 0, 0],          
              [0, 0, 0, 0],          
              [0, 0, 0, 0]];
     
    let position = new Array(15);
    position[0] = [0, 0];
    let direction = [[-1, 0], [0, -1], [1, 0], [0, 1]];
    let destination = [3, 2];
     
    function maze(step) {    
        //结束条件是抵达目的地    
        if (position[step][0] === destination[0] && position[step][1] === destination[1]) {       
            console.log(position);        
            return;    
        }
         
        for (let i = 0; i < 4; i++) {                
            let new_x = position[step][0] + direction[i][0];        
            let new_y = position[step][1] + direction[i][1]; 
                           
            if (new_x < 0 || new_x > 4 || new_y < 0 || new_y > 3) {            
                continue;        
            }
             
            if (ma[new_x][new_y] === 0 && mb[new_x][new_y] === 0) {           
                position[step + 1] = [new_x, new_y];           
                mb[new_x][new_y] = 1;         
                maze(step + 1);           
                mb[new_x][new_y] = 0;       
            }  
        }    
        return;
    }
                       
    maze(0);
    1
    打赏
    收藏
    点击回答
    您的回答被采纳后将获得:提问者悬赏的 11 元积分
        全部回答
    • 0
    • 无就将法 普通会员 1楼

      深度优先搜索(DFS)是一种用于寻找图中所有可能路径的算法。在Python中,我们可以使用递归的方式来实现深度优先搜索。下面是一个简单的例子,用于找出从起点到指定位置的所有路径:

      python def dfs(graph, start, end): if start == end: print("Path found!") return for neighbor in graph[start]: if neighbor == end: print("Path found!") return dfs(graph, neighbor, end)

      在这个例子中,graph是一个字典,其中键是节点,值是一个列表,包含了从当前节点到该节点的所有邻居节点。startend是你想要搜索的节点。

      如果你想要打印出所有路径,你可以稍微修改一下上面的代码:

      python def dfs(graph, start, end): print("Path found!") print("1 ->", start) for neighbor in graph[start]: if neighbor == end: print("Path found!") print("2 ->", neighbor) print("3 ->", end) return dfs(graph, neighbor, end)

      这个版本的代码会打印出从起点到指定位置的所有路径,以及路径的编号。你可以根据需要修改输出格式。

    更多回答
    扫一扫访问手机版
    • 回到顶部
    • 回到顶部