12.矩阵中的路径（回溯法）

一、回溯法

回溯法可以看做蛮力法的升级版，它从解决问题每一步的所有可能选项里系统地选择出一个可行的解决方案。回溯法非常适合有多个步骤组成的问题，并且每个步骤都有多个选项。当我们在某一步选择了其中一个选项时，就进入下一步，然后有面临新的选择。我们这样重复选择，直至达到最终状态。

用回溯法解决的问题的所有选项可以形象的用树状结构表示。在某一步有n个可能的选项，那么该步骤可以看成是树状结构的一个节点，每个选项可以看做树中节点的联线，经过这些联线到达该节点的n个子节点。树的叶节点对应着终结状态。

流程：

• 如果在叶节点的状态满足题目的越苏条件时，那么我们找到了一个可行的解决方案。

• 如果在叶节点的状态不满足约束条件，那么只好回溯到它的上一个节点，在尝试其他的选项。

• 如果上一个节点，所有可能的选项多已经试过了，并且不能达到满足条件的最终状态，则再次回溯到上一个节点。

• 如果所有节点的所有选项都已经尝试过，仍然不能达到满足约束条件的终结状态，则无解。

二、典型题目

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

例如，在下面的 3×4 的矩阵中包含单词 "ABCCED"（单词中的字母已标出）。

|A|B|C|E|
|S|F|C|S|
|A|D|E|E|

示例 1：

 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
 输出：true

示例 2：

 输入：board = [["a","b"],["c","d"]], word = "abcd"
 输出：false

提示：

 1 <= board.length <= 200
 1 <= board[i].length <= 200
 board 和 word 仅由大小写英文字母组成

注意：本题与主站 79 题相同：https://leetcode-cn.com/problems/word-search/

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

三、解法

解法

⭐GitHub

 func exist(_ board: [[Character]], _ word: String) -> Bool {
    let maxY = board.count
    let chars: [Character] = Array(word)

    guard let maxX = board.first?.count, maxY > 0, maxX > 0 else {
        return false
    }

    // 用于保存访问状态
    var visited: [[Bool]] = Array(repeating: Array(repeating: false, count: maxX), count: maxY)

    var pathLength = 0

    for y in 0..<maxY {
        for x in 0..<maxX {
            if hasPathCore(board, chars, maxX: maxX, maxY: maxY, pathLength: &pathLength, x: x, y: y, visted: &visited) {
                return true
            }
        }
    }

    return false
}

func hasPathCore(_ board: [[Character]], _ chars: [Character], maxX: Int, maxY: Int, pathLength: inout Int, x: Int, y: Int, visted: inout [[Bool]]) -> Bool {
    if pathLength == chars.count {
        return true
    }

    var result = false
    if x >= 0, y >= 0,
       x < maxX, y < maxY,
       visted[y][x] == false,
       board[y][x] == chars[pathLength]
    {
        pathLength += 1
        visted[y][x] = true

        result =
            hasPathCore(board, chars, maxX: maxX, maxY: maxY, pathLength: &pathLength, x: x - 1, y: y, visted: &visted) ||
            hasPathCore(board, chars, maxX: maxX, maxY: maxY, pathLength: &pathLength, x: x + 1, y: y, visted: &visted) ||
            hasPathCore(board, chars, maxX: maxX, maxY: maxY, pathLength: &pathLength, x: x, y: y - 1, visted: &visted) ||
            hasPathCore(board, chars, maxX: maxX, maxY: maxY, pathLength: &pathLength, x: x, y: y + 1, visted: &visted)

        if result == false {
            pathLength -= 1
            visted[y][x] = false
        }
    }

    return result
}

四、本题考点

• 考察对回溯法的理解。通常在二维矩阵上找路径都可以使用回溯法解决

• 考察对数组的编程能力。我们一般都把矩阵看成是儿歌二维数组。只有对数组的特性充分了解，才能快速、正确地实现回溯法的代码。