Py小郑 2022-02-21 09:18 采纳率: 96.6%
浏览 84
已结题

Python 有关DFS求解迷宫问题

img


有个地方不懂:就是如果newpoint合法,那么标记当前的点为1,继续深搜newpoint.也就是point[x][y]=1
dfs(newx,newy)这里可以理解,因为防止走回头路。那么为什么对newpoint深搜完了以后,要把原来的point设置为0呢(可访问),如果不加会导致什么?这里搞不灵清,请求指教!

  • 写回答

2条回答 默认 最新

  • 愿此后再无WA Python领域新星创作者 2022-02-21 09:54
    关注

    嗨小郑,谢邀!我还没刷到迷宫类问题,我就从DFS角度讲一下:它是回溯算法中的一个特点:状态重置。dfs就是从一个点开始不断回溯寻找下一个位置,当找到目标位置或者不满足条件时就要回退到上一个位置往其他位置寻找,当这个位置也不满足条件时需要继续回退,以此类推。如果不将point改成0的话当找到当走完一个位置是point数组全都标记成1了,无法继续寻找。等我给你弄个gif

    img

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 3月1日
  • 已采纳回答 2月21日
  • 创建了问题 2月21日