回溯迷宫找终点

╰+攻爆jí腚メ 2021-12-18 13:23 250阅读 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 条评论，250人围观）

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

相关阅读

相关搜索与回溯：迷宫

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

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

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

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

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

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

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

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

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

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

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

相关 Java实现迷宫回溯

[点击进入尚硅谷数据结构和算法Java代码导航][Java] 算法还是蛮有意思的，这个算法可以找到通路，但不是最优解。迷宫最短路径参考：https://blog.csdn.n

雨点打透心脏的1/2处/ 2023年07月10日 12:59/ 0 赞/ 2 阅读

相关递归：回溯，迷宫，八皇后问题

1，递归的基本原则执行一个方法时，就创建一个新的受保护的独立空间（JVM栈）方法的局部变量是独立的，不会相互影响方法中使用的是引用类型变量，则会基

布满荆棘的人生/ 2023年02月27日 13:58/ 0 赞/ 39 阅读

相关回溯法解决迷宫问题

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

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

相关递归实现迷宫找路径

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

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

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

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

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

相关回溯迷宫找终点

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

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