题目

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 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个方向都不存在路径，也记得要将标志位清空，避免干扰其他路径遍历时候经过该点

代码

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
}