题解 | #矩阵中的路径# 11-1 04 dfs + 回溯 定界

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型vector<vector<>> 
     * @param word string字符串 
     * @return bool布尔型
     */
    bool flag = false;
    bool hasPath(vector<vector<char> >& matrix, string word) {
        // write code here
        int column = matrix.size(), line = matrix[0].size();
        if (column == 0 || word.size() == 0) {
            return false;
        }
        vector<vector<bool>> visited (column, vector<bool>(line, false));
        for (int i = 0; i < column; i++) {
            for (int j = 0; j < line; j++) {
                if (matrix[i][j] == word[0]) {
                    dfs(i, j, 0, word, matrix, visited);
                    if (flag) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
    
    void dfs(int x, int y, int curr, string &word, vector<vector<char> >& matrix, vector<vector<bool> >& visited) {
        // 定界
        if (flag || curr >= word.size()) {
            return;
        }
        
        if(x < 0 || x >= matrix.size() || y < 0 || y >= matrix[0].size() || matrix[x][y] != word[curr]) {
            return;
        }
        
        if (visited[x][y]) {
            return;
        }
        

        if (curr == word.size() - 1) {
            flag = true;
            return;
        }
        
        // 回溯
        visited[x][y] = true;
        
        dfs(x + 1, y, curr + 1, word, matrix, visited);
        dfs(x - 1, y, curr + 1, word, matrix, visited);
        dfs(x, y + 1, curr + 1, word, matrix, visited);
        dfs(x, y - 1, curr + 1, word, matrix, visited);

        visited[x][y] = false;
    }
};