CS-Notes 剑指 Offer 题解：用回溯法求解"矩阵中的路径"

2026-09-06 11:28:22作者：侯霆垣

本文基于 CS-Notes 仓库中 notes/12. 矩阵中的路径.md 一篇题解展开，完整讲解这道经典回溯（backtracking）搜索题的建模思路、剪枝条件设计与状态回退机制，并给出可直接运行的完整 Java 实现。读完后你将掌握：如何把"网格中找路径"这类问题转化为状态空间树搜索，如何用 marked 数组实现"设置状态—回溯清除"，以及如何对解法做时间/空间复杂度分析。

一、题目描述

判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向上下左右移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。

例如下面的矩阵包含了一条 bfce 路径：

题目输入有两个容易忽视的约束：

输入是数组而不是矩阵：矩阵内容以一维字符串（数组）形式给出，需要结合行列数自行还原为二维矩阵；
起点不固定：路径可以从任意格子出发，因此需要对每个格子都尝试一次，任何一个起点走通即返回 true。

二、解题思路：回溯法

使用回溯法（backtracking）进行求解，它是一种暴力搜索方法，通过搜索所有可能的结果来求解问题。回溯法在一次搜索结束时需要进行回溯（回退），将这一次搜索过程中设置的状态进行清除，从而开始一次新的搜索过程。

如上图示例中，从 f 开始，下一步有 4 种搜索可能。如果先搜索 b，需要将 b 标记为已经使用，防止重复使用；在这一次搜索结束之后，需要将 b 的"已经使用"状态清除，再搜索 c。这正体现了回溯法的两个核心动作：

做选择（设置状态）：进入某个格子时，将其标记为已访问；
撤销选择（状态回退）：从该格子返回时，必须把标记清除，否则后续从其他起点出发的搜索会被错误的 visited 状态污染。

与普通的深度优先搜索（DFS）相比，回溯是 DFS 的一种特例：DFS 通常只需要全局的"访问过"标记即可，而回溯法在搜索过程中需要设置本次搜索路径上的局部状态，并在本次搜索结束后逐一清除。这一点也可以结合仓库中下一题 13. 机器人的运动范围的讨论对照理解——那道题用普通 DFS 计数可达格子，不需要状态回退；而本题要求"单条路径内不重复进入格子"，因此必须使用带回退的 marked 数组。

三、完整 Java 实现与逐段解析

下面是 notes/12. 矩阵中的路径.md 中给出的完整解法，包含一维数组到矩阵的转换、方向数组、回溯主体与测试入口：

public class Solution {
    private final static int[][] next = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
    private int rows;
    private int cols;

    public boolean hasPath (String val, int rows, int cols, String path) {
        if (rows == 0 || cols == 0) return false;
        this.rows = rows;
        this.cols = cols;
        char[] array = val.toCharArray();
        char[][] matrix = buildMatrix(array);
        char[] pathList = path.toCharArray();
        boolean[][] marked = new boolean[rows][cols];
        for (int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++)
                if (backtracking(matrix, pathList, marked, 0, i, j))
                    return true;

        return false;
    }

    private boolean backtracking(char[][] matrix, char[] pathList,
                                 boolean[][] marked, int pathLen, int r, int c) {

        if (pathLen == pathList.length) return true;
        if (r < 0 || r >= rows || c < 0 || c >= cols
                || matrix[r][c] != pathList[pathLen] || marked[r][c]) {

            return false;
        }
        marked[r][c] = true;
        for (int[] n : next)
            if (backtracking(matrix, pathList, marked, pathLen + 1, r + n[0], c + n[1]))
                return true;
        marked[r][c] = false;
        return false;
    }

    private char[][] buildMatrix(char[] array) {
        char[][] matrix = new char[rows][cols];
        for (int r = 0, idx = 0; r < rows; r++)
            for (int c = 0; c < cols; c++)
                matrix[r][c] = array[idx++];
        return matrix;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String val = "ABCESFCSADEE";
        int rows = 3;
        int cols = 4;
        String path = "ABCCED";
        boolean res = solution.hasPath(val, rows, cols, path);
        System.out.println(res);
    }
}

运行 main 中的用例（矩阵 ABCESFCSADEE，3 行 4 列，路径 ABCCED）会输出 true。

3.1 一维数组转二维矩阵

buildMatrix 负责题目约束 1 中提到的格式转换：利用一个递增下标 idx，把一维字符数组按"先行后列"的顺序依次填入 char[rows][cols]，保证 array[r * cols + c] 与 matrix[r][c] 一一对应。

3.2 方向数组与"起点不固定"的外层循环

next 静态数组 {{0, -1}, {0, 1}, {-1, 0}, {1, 0}} 把"上下左右"四方向编码为行列偏移量，回溯函数只需对四个偏移做同一段递归逻辑，避免写四份重复代码。

hasPath 的双层 for 循环遍历所有格子 (i, j)，把每个格子都当作回溯的候选起点；一旦某个起点走通了（backtracking 返回 true），立即向外返回 true，不再尝试其余起点。注意 marked 数组只创建一次、在整个搜索期间复用——这要求每次失败返回时标记必须已经被回退干净，代码中靠 marked[r][c] = false 这一行保证。

3.3 回溯函数：先判终止、再剪枝、后回退

backtracking 函数按三个顺序清晰的阶段工作：

成功终止条件：pathLen == pathList.length 说明路径字符已全部匹配完成，返回 true。这个判断放在函数最前面，意味着"匹配完最后一个字符的那个格子"不需要再向四周扩展；
剪枝（失败）条件：以下任一情况成立则本次分支必然失败，直接返回 false：
- 越界：r < 0 || r >= rows || c < 0 || c >= cols（必须最先判断，否则后面的数组访问会越界）；
- 字符不匹配：matrix[r][c] != pathList[pathLen]；
- 已被访问：marked[r][c]。三个条件用短路求值的 || 串联，越界检查先行，从结构上杜绝了数组越界异常；
做选择 → 递归 → 撤销选择：把当前格子标记为已访问（marked[r][c] = true），对四个方向逐一递归；任一方向成功则整体成功并提前返回；否则在函数末尾把标记恢复为 false 再返回 false——这就是"状态回退"，是整道题目解正确性的关键。

四、边界情况与易错点

空矩阵输入：hasPath 开头对 rows == 0 || cols == 0 直接返回 false，避免后续 new char[0][0] 与无意义搜索；
visited 状态的作用域：marked 标记的是"当前这一条候选路径"上已使用的格子，而不是"矩阵中所有曾尝试过的格子"。如果把 marked[r][c] = false 的回退行漏掉，第二条从其他起点出发的路径会误判格子为已占用，导致漏解；
路径长度大于矩阵格子数：例如 path.length() > rows * cols 时必然无解，解法会通过逐层失败自然返回 false；在面试中也可以把它作为显式剪枝提前判断；
起点枚举与提前退出：外层循环在任一起点成功时立刻返回，最坏情况才需要遍历全部 rows * cols 个起点。

五、复杂度分析

设矩阵规模为 m × n，路径长度为 L：

时间复杂度：最坏情况下每个起点都会展开一棵深度为 L、分支因子至多为 4 的搜索树，单起点搜索代价为 O(4^L) 量级（实际受剪枝影响，字符不匹配、越界、已访问都会提前截断分支），整体最坏为 O(m·n·4^L)。字符不匹配的剪枝使实际运行远好于最坏估计；
空间复杂度：marked 数组 O(m·n)，矩阵副本 O(m·n)，递归栈深度 O(L)，合计 O(m·n + L)。