题解 | 矩阵中的路径

#include <cstddef>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param matrix char字符型vector<vector<>>
     * @param word string字符串
     * @return bool布尔型
     */

    bool checkOnePoint(vector<vector<char>>& matrix, vector<vector<bool> >& hasDone, int posWord, string word, int h, int l) {

        if(!(h < matrix.size() && h >= 0 && l < matrix[0].size() && l >= 0 && !hasDone[h][l])){
            return false;
        }
        else if(word[posWord]!=matrix[h][l]) return false;
        hasDone[h][l] = true;
        if(posWord==word.size()-1)return true;
        bool ans = checkOnePoint(matrix, hasDone, posWord+1, word, h+1, l)||checkOnePoint(matrix, hasDone, posWord+1, word, h-1, l)||checkOnePoint(matrix, hasDone, posWord+1, word, h, l+1)||checkOnePoint(matrix, hasDone, posWord+1, word, h, l-1);
        hasDone[h][l] = false;
        return ans;
    }
    bool hasPath(vector<vector<char> >& matrix, string word) {
        // write code here
        if (matrix.empty() || word.size() == 0) return false;

        for (int i = 0; i < matrix.size(); ++i) {
            for (int j = 0; j < matrix[0].size(); ++j) {
                int row = matrix.size();//行
                int line = matrix[0].size();//列
                vector<vector<bool> > hasDone(row, vector<bool>(line, false));
                bool ans = checkOnePoint(matrix, hasDone, 0, word, i, j);
                if(ans) return true;
            }
        }
        return false;
    }
};

想了好久有没有简单解法，毕竟标的是中级，如果遍历再dfs未免时间和空间都消耗太大，可能过不了。

想不出来就交了，发现过了，再看题解也是遍历+dfs，dfs标什么中级（）

唯一大家要注意的点就是进入深处时标记为访问过，等你退出对它的访问（访问这个点的函数返回）时，要先标记为未访问过。

因为这说明这条路不通，但是如果上面走了其他的路，又经过这个节点时所处word字符串位置不一样了还可能走通的。

时间复杂度为O(mn(3^word.size())，空间复杂度为O(mn+word.size())。