剑指offer刷题记录9--矩阵中的路径(深度优先搜索+回溯)
该系列博客内容主要是《剑指Offer》中的经典题目,结合在刷题过程中见到的一些精彩的解题过程,从而在这里记录下来。代码以Python3实现。
题目分析
这道题,只能使用暴力DFS(深度优先搜索)+ 剪枝来做,就是依次遍历二维矩阵上面所有的元素,若和给定的单词第一个字母匹配,那么我们便从这个字母开始,依次看他的上下左右方向的节点是不是和单词的第二个字母匹配,一旦有一个不匹配,后面的就不需要比较,直接返回上一个节点的其他方向。当所有字母单词都匹配完毕,就可以终止遍历二维矩阵了,返回True。若所有的节点都查看完毕,还没有整体匹配的,返回False。在这里需要注意的是,不许利用重复的节点,我们可以在判断当前节点等于单词上的某个字母之后,把这个节点的值进行修改,等到下一个节点遍历返回结果的时候再修改回来。
下面来说一说这道题所涉及的算法思想。
回溯
回溯实际上是一种试探算法,这种算法跟暴力搜索最大的不同在于,在回溯算法里,是一步一步地小心翼翼地进行向前试探,会对每一步探测到的情况进行评估,如果当前的情况已经无法满足要求,那么就没有必要继续进行下去,也就是说,它可以帮助我们避免走很多的弯路。
回溯算法的特点在于,当出现非法的情况时,算法可以回退到之前的情景,可以是返回一步,有时候甚至可以返回多步,然后再去尝试别的路径和办法。这也就意味着,想要采用回溯算法,就必须保证,每次都有多种尝试的可能。
解题步骤:
1.判断当前情况是否非法,如果非法就立即返回;
2.当前情况是否已经满足递归结束条件,如果是就将当前结果保存起来并返回;
3.当前情况下,遍历所有可能出现的情况并进行下一步的尝试;
4.递归完毕后,立即回溯,回溯的方法就是取消前一步进行的尝试。
深度优先搜索(Depth First Search/ DFS)
深度优先搜索,从起点出发,从规定的方向中选择其中一个不断地向前走,直到无法继续为止,然后尝试另外一种方向,直到最后走到终点。就像走迷宫一样,尽量往深处走。
DFS 解决的是连通性的问题,即,给定两个点,一个是起始点,一个是终点,判断是不是有一条路径能从起点连接到终点。起点和终点,也可以指的是某种起始状态和最终的状态。问题的要求并不在乎路径是长还是短,只在乎有还是没有。有时候题目也会要求把找到的路径完整的打印出来。
DFS遍历
例题:假设我们有这么一个图,里面有A、B、C、D、E、F、G、H 8 个顶点,点和点之间的联系如下图所示,对这个图进行深度优先的遍历。
解题思路
必须依赖栈(Stack),特点是后进先出(LIFO)。
第一步,选择一个起始顶点,例如从顶点 A 开始。把 A 压入栈,标记它为访问过(用红色标记),并输出到结果中。
第二步,寻找与 A 相连并且还没有被访问过的顶点,顶点 A 与 B、D、G 相连,而且它们都还没有被访问过,我们按照字母顺序处理,所以将 B 压入栈,标记它为访问过,并输出到结果中。
第三步,现在我们在顶点 B 上,重复上面的操作,由于 B 与 A、E、F 相连,如果按照字母顺序处理的话,A 应该是要被访问的,但是 A 已经被访问了,所以我们访问顶点 E,将 E 压入栈,标记它为访问过,并输出到结果中。
第四步,从 E 开始,E 与 B、G 相连,但是B刚刚被访问过了,所以下一个被访问的将是G,把G压入栈,标记它为访问过,并输出到结果中。
第五步,现在我们在顶点 G 的位置,由于与 G 相连的顶点都被访问过了,类似于我们走到了一个死胡同,必须尝试其他的路口了。所以我们这里要做的就是简单地将 G 从栈里弹出,表示我们从 G 这里已经无法继续走下去了,看看能不能从前一个路口找到出路。
可以看到,每次我们在考虑下一个要被访问的点是什么的时候,如果发现周围的顶点都被访问了,就把当前的顶点弹出。
第六步,现在栈的顶部记录的是顶点 E,我们来看看与 E 相连的顶点中有没有还没被访问到的,发现它们都被访问了,所以把 E 也弹出去。
第七步,当前栈的顶点是 B,看看它周围有没有还没被访问的顶点,有,是顶点 F,于是把 F 压入栈,标记它为访问过,并输出到结果中。
第八步,当前顶点是 F,与 F 相连并且还未被访问到的点是 C 和 D,按照字母顺序来,下一个被访问的点是 C,将 C 压入栈,标记为访问过,输出到结果中。
第九步,当前顶点为 C,与 C 相连并尚未被访问到的顶点是 H,将 H 压入栈,标记为访问过,输出到结果中。
第十步,当前顶点是 H,由于和它相连的点都被访问过了,将它弹出栈。
第十一步,当前顶点是 C,与 C 相连的点都被访问过了,将 C 弹出栈。
第十二步,当前顶点是 F,与 F 相连的并且尚未访问的点是 D,将 D 压入栈,输出到结果中,并标记为访问过。
第十三步,当前顶点是 D,与它相连的点都被访问过了,将它弹出栈。以此类推,顶点 F,B,A 的邻居都被访问过了,将它们依次弹出栈就好了。最后,当栈里已经没有顶点需要处理了,我们的整个遍历结束。
掌握了这两个算法后,我们再回过头来看看这道题。
来自力扣大佬的解析
代码
代码中比较难理解的部分:
1.为啥最后需要用board[i][j]=tmp来还原元素?
递归搜索匹配字符串过程中,需要board[i][j] = ‘1’ 来防止 ”走回头路“ 。当匹配字符串不成功时,会回溯返回,此时需要board[i][j] = tmp 来”取消对此单元格的标记”。 在DFS过程中,每个单元格会多次被访问的, board[i][j] = '1’只是要保证在当前匹配方案中不要走回头路。在这里的话,因为是一层一层向下递归来进行字符串匹配的,回溯的时候要“释放“这个单元格。匹配失败或者成功都会执行 board[i][j] = tmp
2.代码中最后两个for循环是因为我们并不能确定 “字符串的起始点在矩阵中的位置” ,有可能是 (0, 0) , (0, 1) … 等等。 因此需要遍历矩阵,从矩阵的每个单元格开启搜索。(每次搜索只能搜到 以此单元格为起始的字符串方案)