关于java:12-矩阵中的路径深度优先搜索DFS

43次阅读

共计 471 个字符,预计需要花费 2 分钟才能阅读完成。

153. 寻找旋转排序数组中的最小值


深度优先搜寻(DFS)

本问题是典型的 矩阵搜寻 问题,可应用 深度优先搜寻(DFS)+ 剪枝 解决。
像是在暴力破解
1、遍历矩阵,找到雷同的字符,
2、从这个字符开始递归上下左右的字符,出界和与 word[k+1] 不等则返回 false;
3、若与 word[k+1]雷同,且 k 是最初一个字符,就示意递归完结且有符合条件的字符串,返回 true。
4、若与 word[k+1]雷同,但不是最初一个字符,就示意须要递归,这里比拟暴力了,
上下左右有一个合乎的,就持续递归上来,没有合乎的就中断并返回 false。从矩阵的下一个字符从新找与 word 的第一个字符雷同的。

这里还有一个重点!!:矩阵中的字符只能用一次,所以须要将判断雷同的字符置为空格字符 '\0',如果这条路走不通,即第四步返回了 false,再复原成原样。

操作:

只有有一条路 true 了,就返回 true,所有的路都走不通了等循环完结了才返回 false。

  • 留神:

    • 出界是 i>board.length-1
    • 递归写的时候,感觉都是先写否定的,和跳出递归的,最初写简单的
    • 记得把用过一次的换成 ’\0′

正文完
 0