题解 | #矩阵中的路径#

C++回溯的方法解决问题
需要创建一个记录数组来记录回溯过程中访问的状态，防止回溯过程中重复访问某个元素
需要注意的是，回溯返回时，要对状态值重置
这道题的搜索路径是上下左右四个方向，并且可以从矩阵中的任一个位置开始回溯，所以要对矩阵中的每一个位置进行回溯，如果回溯中遇到了契合的字符串，则直接返回true

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型vector<vector<>> 
     * @param word string字符串 
     * @return bool布尔型
     */
    void dfs(vector<vector<char>> &matrix, vector<vector<bool>> &flag, string curword, int i, int j) {
        // 可向上下左右四个方向去探索
        // count用于计数，判断当前字符串加到哪里了
        if (i < 0 || i > matrix.size() - 1 || j < 0 || j > matrix[0].size() - 1) return;
        if (!flag[i][j]) return;
        if (matrix[i][j] == target[curword.size()]) {
            curword += matrix[i][j];
            flag[i][j] = false;
        }
        else return;

        if (curword.size() == target.size()) {
            haspath = true;
            return;
        } else {
            dfs (matrix, flag, curword, i+1, j);
            if (haspath) return;
            dfs (matrix, flag, curword, i-1, j);
            if (haspath) return;
            dfs (matrix, flag, curword, i, j-1);
            if (haspath) return;
            dfs (matrix, flag, curword, i, j+1);
        }
        flag[i][j] = true;  // 回溯，回来后要记得修改状态
        return;

    }

    bool hasPath(vector<vector<char> >& matrix, string word) {
        // write code here
        // 判断矩阵中是否有一个路径是否和word相同
        // 理应用回溯法来做
        target = word;
        flag = vector<vector<bool>>(matrix.size(), vector<bool>(matrix[0].size(), true));
        for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[0].size(); j++) {
                // 对矩阵中的每一个元素，每一个元素都可作为起点
                dfs (matrix, flag, "",i,j);
                if (haspath) return true;
            }
        }
        return haspath;
    }
private:
    bool haspath = false;
    vector<vector<bool>> flag;  // 先定义类型，但并不初始化
    string target;
};