【剑指offer】065-矩阵中的路径

题目

请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串”bcced”的路径,但是矩阵中不包含”abcb”路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。

方法

方法:回溯法
代码格式参考:
递归写法:https://www.cnblogs.com/yongh/p/9655745.html
if条件写法:http://wiki.jikexueyuan.com/project/for-offer/question-sixty-six.html

思路

本题思路主要就是回溯
由于每个点出发都有可能存在与path完全相等的路径,所以需要两层循环,从每个点出发去寻找是否有path路径
从一个点出发,如果这个点和比对路径path的首位相等,就往上右下左4个方向延伸
继续比较,如果某个方向上的点,与path第二个字符相等,就从这个点,继续向4个方向延伸比较
以此类推,一直深入
对于某个点,上右下左只要有1个方向存在路径,该点就存在path路径。这样的规则,针对回溯过程中遍历到某个点时也是适用的,只不过是比较path路径的一部分

注意:

  1. 走过每个点,需要设置标志位,表示已经遍历过,当前路径不可再经过该点
  2. 如果该点出发的4个方向都不存在路径,也记得要将标志位清空,避免干扰其他路径遍历时候经过该点

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
function hasPath (matrix, rows, cols, path{
  // write code here
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      let flag = new Array(matrix.length).fill(false)
      let pathLength = 0
      if (isPath(matrix, i, j, path, pathLength, flag, rows, cols)) return true
    }
  }
  return false
}
function isPath (matrix, i, j, path, pathLength, flag, rows, cols{
  // path完全相等,路径匹配成功
  if (pathLength === path.length) return true
  // 越界
  let pos = i * cols + j
  if (
    (i < 0 || i >= rows) ||
    (j < 0 || j >= cols) ||
    flag[pos] === true ||
    matrix[pos] !== path[pathLength]
  ) return false
  // 当前位相同
  flag[pos] = true
  // 判断四项,递归。上右下左,如有其中一条路走通了,就算ok
  let hasPath =
    isPath(matrix, i - 1, j, path, pathLength + 1, flag, rows, cols) ||
    isPath(matrix, i, j + 1, path, pathLength + 1, flag, rows, cols) ||
    isPath(matrix, i + 1, j, path, pathLength + 1, flag, rows, cols) ||
    isPath(matrix, i, j - 1, path, pathLength + 1, flag, rows, cols)
  if (hasPath) return true
  else flag[pos] = false
}
文章作者: ptp
文章链接: https://youyingjie114.github.io/2019/11/07/jz-offer/jz-offer-065/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 PTP'S BLOG