# 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：

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

示例 2：

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

提示：

```cpp
 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> 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 三、解法

![解法](/files/-MeEyikK3rFTeYqXSsdH)

[⭐GitHub](https://github.com/RyukieSama/RyukiePlayground/blob/main/剑指Offer.playground/Pages/⭐%EF%B8%8F⭐%EF%B8%8F12.矩阵中的路径（回溯法）.xcplaygroundpage/Contents.swift)

```swift
 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
}
```

## 四、本题考点

* 考察对回溯法的理解。通常在二维矩阵上找路径都可以使用回溯法解决
* 考察对数组的编程能力。我们一般都把矩阵看成是儿歌二维数组。只有对数组的特性充分了解，才能快速、正确地实现回溯法的代码。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://ryukiedev.gitbook.io/wiki/shu-ju-jie-gou-yu-suan-fa/jian-zhi-offerswift/12.-ju-zhen-zhong-de-lu-jing-hui-su-fa.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.