题解 | #迷宫问题#

迷宫问题

http://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc

while(line = readline()){
    const [m,n] = line.split(' ').map(item => item - 0)
    const arr = []
    for(let i = 0; i < m; i++){
        arr.push(readline().split(' ').map(item => item - 0))
    }
    // 1 表示走过,0 表示没走过
    const map = new Array(m).fill().map(() => new Array(n).fill(0))
    // 保存路线的队列
    const queue = []
    // 上下左右四个移动方向
    const flag = [[0,1],[1, 0], [0,-1],[-1 , 0]]
    let over = false
    const dp = (i,j) => {
       // 标记当前已经通过了
        if(over ) return
       // 走到最后位置了
        if(i === m-1 && j == n-1) {
            over = true
            queue.push([i,j])
            return true
        }
      	// 坐标出边界、碰到墙了、之前走过(说明之前没走通) 直接返回函数,后面不用走了
        if(i < 0 || j < 0 || i == m || j== n || arr[i][j] || map[i][j]){
            return false
        }
      	// 走过,后面碰到都不用走了
        map[i][j] = 1
        
        for(let index = 0 ; index< 4 ; index++){
           // 将当前坐标保存到路线队列中
            queue.push([i,j])
            dp(i + flag[index][0], j + flag[index][1])
                if(over)break
            	// 回溯
                queue.pop()
        }
    }
    dp(0,0)
    queue.forEach(item => {
        console.log(`(${item[0]},${item[1]})`)
    })
}
全部评论

相关推荐

07-09 18:33
门头沟学院 Java
这么逆天每年都有人去???&nbsp;填多益网申就是大型的服从性测试
鲁大牛:辅导员在群里发了这个公司我就申了一下。网申居然要写当场开摄像头写两篇不少于三百字的作文。太逆天了
点赞 评论 收藏
分享
06-22 10:41
赣东学院 Java
程序员小白条:?周六晚上投,这是什么操作,专门找996起步的吗
点赞 评论 收藏
分享
哈哈哈哈哈哈哈哈哈哈这个世界太美好了
凉风落木楚山秋:毕业出路老师不管,你盖个章他好交差就完事了,等你盖完毕业了就不关他事情了
点赞 评论 收藏
分享
评论
1
2
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务