回溯迷宫找终点

╰+攻爆jí腚メ 2021-12-18 13:23 229阅读 0赞

## 迷宫找出口 ##

![image][]

function isSafe(maze,x,y){
        if(x >= 0 && y >= 0 && x < maze.length && y < maze.length && maze[x][y] !== 0){
            return true
        }
        return false
    }
    
    function findPath(maze,solution,x,y){
        if( x === solution.length - 1 && y === solution[0].length - 1){
            solution[x][y] = 1
            return true
        }
    
        if(isSafe(maze,x,y)){
            solution[x][y] = 1
            if(findPath(maze,solution,x + 1,y)){
                return true
            }
            if(findPath(maze,solution,x, y + 1)){
                return true
            }
            solution[x][y] = 0
        }
    
        return false
    }
    
    function ratInAMaze(maze){
        let solution = []
        for(let i = 0; i < maze.length; i++){
            solution[i] = []
            for(let j = 0; j < maze[0].length; j++){
                solution[i][j] = 0
            }
        }
        
        if(findPath(maze,solution,0,0)){
            return solution
        }
    
        return 'not solution exsit'
    }
    
    const maze = [
        [1, 0, 0, 0],
        [1, 1, 1, 1],
        [0, 0, 1, 0],
        [0, 1, 1, 1]
      ];
      
    console.log(ratInAMaze(maze));

转载于:https://www.cnblogs.com/pluslius/p/10884222.html

[image]: /images/20211218/8a79b59405424fb4bda971a0facdc5c4.png

发表评论取消回复

表情：

评论列表（有 0 条评论，229人围观）

还没有评论，来说两句吧...

相关阅读

相关搜索与回溯：迷宫

1215：迷宫时间限制: 1000 ms 内存限制: 65536 KB 提交数: 14993 通过数: 4360 【题目描述】一天Extense...

秒速五厘米/ 2024年04月19日 08:49/ 0 赞/ 78 阅读

相关数据结构与算法之迷宫回溯

什么是回溯？回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜...

待我称王封你为后i/ 2024年04月17日 20:42/ 0 赞/ 62 阅读

相关华为OD机试 - 找终点（Java）

题目描述给定一个正整数数组，设为nums，最大为100个成员，求从第一个成员开始，正好走到数组最后一个成员，所使用的最少步骤数。要求： 1. 第一步必须从第一元

缺乏、安全感/ 2024年03月17日 14:15/ 0 赞/ 47 阅读

相关华为OD机试 - 找终点（Java & JS & Python）

题目描述给定一个正整数数组，设为nums，最大为100个成员，求从第一个成员开始，正好走到数组最后一个成员，所使用的最少步骤数。要求： 1. 第一步必须从第一元

矫情吗；*/ 2023年09月26日 10:34/ 0 赞/ 140 阅读

相关华为od统一考试B卷【找终点】C++ 实现

所有题目均有五种语言实现。[C实现目录][C]、[C++ 实现目录][C_]、[Python实现目录][Python]、[Java实现目录][Java]、[JavaScrip

小鱼儿/ 2023年09月23日 13:10/ 0 赞/ 119 阅读

相关 java遍历迷宫代码,java：广度首次遍历与迷宫回溯

我正试图在迷宫中实现广度优先遍历。这是我迄今使用链表的代码，但我不确定它是否首先搜索宽度。这是做到这一点的正确方法吗？任何建议，意见？ public boolean trav

悠悠/ 2023年01月13日 09:13/ 0 赞/ 95 阅读

相关回溯法解决迷宫问题

import java.awt.Point; import java.util.ArrayList; /回溯法走迷宫定义一个二维

淡淡的烟草味﹌/ 2022年09月30日 10:51/ 0 赞/ 166 阅读

相关递归实现迷宫找路径

package com.example.datastructrue.reback; public class MiGong {

蔚落/ 2022年09月08日 03:56/ 0 赞/ 196 阅读

相关数据结构-迷宫问题（回溯法）

> 题目描述：迷宫是一个二维矩阵,其中1为墙,0为路,入口在第一列,出口在最后一行。要求从入口开始,从出口结束,按照上,下,左,右的顺序来搜索路径.。 >

Bertha 。/ 2022年06月04日 09:42/ 0 赞/ 357 阅读

相关回溯迷宫找终点

迷宫找出口 ![image][] function isSafe(maze,x,y){ if(x >= 0 && y >= 0 && x < m

╰+攻爆jí腚メ/ 2021年12月18日 13:23/ 0 赞/ 230 阅读