题解 | #矩阵中的路径#

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param matrix char字符型vector<vector<>>
     * @param word string字符串
     * @return bool布尔型
     */
    bool is_valid(vector<vector<char>>& matrix, vector<vector<bool>>& visited,
                  int i, int j, string& word, int k) {
        // 判断边界条件
        if (i < 0 || i >= matrix.size() || j < 0 || j >= matrix[0].size()) {
            return false;
        }
        // 判断是否已经访问过或者不匹配
        if (visited[i][j] || matrix[i][j] != word[k]) {
            return false;
        }
        // 返回真值
        return true;
    }
    bool find_path(vector<vector<char>>& matrix, vector<vector<bool>>& visited,
                   int i, int j, string& word, int k) {
        // 判断是否已经找到了路径
        if (k == word.size()) {
            return true;
        }
        // 判断当前位置是否有效
        if (!is_valid(matrix, visited, i, j, word, k)) {
            return false;
        }
        // 标记当前位置为已访问
        visited[i][j] = true;
        // 尝试四个方向的移动
        bool res = find_path(matrix, visited, i - 1, j, word, k + 1) ||
                   find_path(matrix, visited, i + 1, j, word, k + 1) ||
                   find_path(matrix, visited, i, j - 1, word, k + 1) ||
                   find_path(matrix, visited, i, j + 1, word, k + 1);
        // 回溯，恢复当前位置为未访问。因为此时失败了，所以回到起点，尝试其他选择，将当前点标记为false，不影响下一次尝试。
        visited[i][j] = false;
        // 返回结果
        return res;
    }
    bool hasPath(vector<vector<char> >& matrix, string word) {
        // write code here
        // 判断特殊情况
        if (matrix.empty() || matrix[0].empty() || word.empty()) {
            return false;
        }
        // 获取矩阵的行数和列数
        int n = matrix.size();
        int m = matrix[0].size();
        // 创建一个二维布尔数组，用来记录访问状态
        vector<vector<bool>> visited(n, vector<bool>(m));
        // 遍历矩阵的每个位置，作为路径的起点
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 如果找到了路径，返回真值
                if (find_path(matrix, visited, i, j, word, 0)) {
                    return true;
                }
            }
        }
        // 如果没有找到路径，返回假值
        return false;
    }
};