题解 | #矩阵中的路径#

#include <vector>
class Solution {
public:
    bool hasPath(vector<vector<char> >& matrix, string word) {
        if (matrix.empty()) return false;
        int rows = matrix.size();
        int cols = matrix[0].size();
        vector<vector<bool> > state(rows, vector<bool>(cols, false));
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (dfs(matrix, rows, cols, i, j, state, word, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    bool dfs(vector<vector<char> >& matrix, int rows, int cols, int i, int j,
        vector<vector<bool> >& state, const string& word, int word_idx) 
    {
        if (i < 0 || i >= rows) return false;
        if (j < 0 || j >= cols) return false;
        if (matrix[i][j] != word[word_idx]) return false;
        if (state[i][j]) return false;
        
        if (word_idx == word.length() - 1) return true;
        state[i][j] = true;
        if (
            dfs(matrix, rows, cols, i-1, j, state, word, word_idx + 1) ||
            dfs(matrix, rows, cols, i+1, j, state, word, word_idx + 1) ||
            dfs(matrix, rows, cols, i, j+1, state, word, word_idx + 1) ||
            dfs(matrix, rows, cols, i, j-1, state, word, word_idx + 1)
        ) {
            return true;
        }
        state[i][j] = false;
        return false;
    }
};