题解 | #矩阵中的路径#

• DFS，与word进行匹配；
• 建立与矩阵大小一样的标志，确保每个元素只使用一次；
• 遍历矩阵中每个元素，作为DFS的初始值；
• 如果已匹配元素个数与word大小相同，返回true；
• 如果当前元素使用过，返回false；
• 如果当前元素与word字符不匹配，返回false；
• 当前元素使用过，标志相应为true；
• 有一项结果满足，返回true；
• 否则，重置标志位，返回false。

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