一、题目描述

JZ65矩阵中的路径
题目大意：请判断一个矩阵是否存在一条包含某字符串所有字符的路径。路径可以从矩阵的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个个子，则该路径不能再进入该格子。
注意审题：不能重复走相同的位置

二、算法（回溯）

解题思路

1. 枚举路径的入口，通过判断矩阵的元素是否等于给定字符串的第一个字符，若相等，就尝试递归找到路径
2. 用一个判重数组标记走过的位置，防止重复走，递归中尝试走每一种走法，剪枝的方法就是判定当前位置和word字符串中对应位置的字符是否相同
3. 当对应上了word字符串的所有字符后，说明找到了一条合法路径，否则未找到

代码实现（C++11）

class Solution {
private:
    static constexpr int maxn = 205;    // 根据题目给出的信息，矩阵最大为200 * 200
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型vector<vector<>> 
     * @param word string字符串 
     * @return bool布尔型
     */
    int vis[maxn][maxn], n, m;    // n为矩阵行数, m为矩阵列数

    const int dxy[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};    // 向四个方向移动的偏移量

    bool hasPath(vector<vector<char>>& matrix, string word) {
        n = matrix.size(), m = matrix[0].size();
        memset(vis, 0, sizeof(vis));    // 初始化
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(matrix[i][j] == word[0]){    // 找到入口点
                    if(dfs(matrix, i, j, 1, word)){
                        return true;
                    }
                    vis[i][j] = false;    // 记得恢复状态
                }
            }
        }
        return false;
    }

    bool dfs(vector<vector<char>>& matrix, int x, int y, int p, string& word){
        if(p == word.size()) return true;    // 找到一条合法路径
        vis[x][y] = true;    // 标记当前位置
        for(int i = 0; i < 4; i++){
            int dx = x + dxy[i][0], dy = y + dxy[i][1];
            if(dx >= 0 && dx < n && dy >= 0 && dy < m && !vis[dx][dy] && matrix[dx][dy] == word[p]){
                if(dfs(matrix, dx, dy, p + 1, word)) return true;
                vis[dx][dy] = false;    // 回溯
            }
        }
        return false;
    }
};

时间复杂度：，n为矩阵的行数, m为矩阵的列数, k为给定字符串的长度，每次向四个方向尝试，回溯深度为k，故每次dfs的时间复杂度为
空间复杂度：，递归的深度不会超过字符串的长度k