题解 | #矩阵中的路径#

#include <vector>
class Solution {
public:
    bool dfs(const vector<vector<char>> &matrix, vector<vector<bool>> &flag_vec, 
    const string &word, const int pos_x, const int pos_y, const int pos_cur) {

        if (pos_cur >= word.size()) return true;
        if (pos_x < 0 || pos_x >= matrix.size() || 
            pos_y < 0 || pos_y >= matrix[0].size())  return false;
        if (flag_vec[pos_x][pos_y] == true) return false;
        if (matrix[pos_x][pos_y] != word[pos_cur]) return false;
        
        flag_vec[pos_x][pos_y] = true;

        bool ret_up = dfs(matrix, flag_vec, word, pos_x - 1, pos_y, pos_cur + 1);
        bool ret_down = dfs(matrix, flag_vec, word, pos_x + 1, pos_y, pos_cur + 1);
        bool ret_left = dfs(matrix, flag_vec, word, pos_x, pos_y - 1, pos_cur + 1);
        bool ret_right = dfs(matrix, flag_vec, word, pos_x, pos_y + 1, pos_cur + 1);

        flag_vec[pos_x][pos_y] = false;

        return ret_up || ret_down || ret_left || ret_right;

    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型vector<vector<>> 
     * @param word string字符串 
     * @return bool布尔型
     */
    bool hasPath(vector<vector<char> >& matrix, string word) {
        // write code here

        if (matrix.empty() || matrix[0].empty()) return false;

        vector<vector<bool>> flag_vec(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 (matrix[i][j] != word[0]) continue;
                if (true == dfs(matrix, flag_vec, word, i, j, 0)) return true;
            }
        }

        return false;
    }
};