class Solution {
public:

    bool dfs(vector<vector<char>> matrix, string str, int k, int x0, int y0){
        //判断当前搜索的位置的字母是否和目标祖母相同
        if(matrix[x0][y0] != str[k])
            return false;
        //一直找到最后一个字母还相同,则返回TRUE
        if(k == str.size() - 1)
            return true;
        int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
        //标记走过的字母
        char t = matrix[x0][y0];
        matrix[x0][y0] = '*';
        for(int i = 0; i < 4; i++){
            int x = x0 + dx[i], y = y0 + dy[i];
            if(0 <= x && x < matrix.size() && 0 <= y && y < matrix[0].size()){
                //若满足条件就返回TRUE
                if(dfs(matrix, str, k + 1, x, y))
                    return true;
            }
        }
        //撤销标记
        matrix[x0][y0] = t;
        return false;
    }
    bool hasPath(vector<vector<char>>& matrix, string &str) {
        //遍历数组
        for(int i = 0; i < matrix.size(); i++){
            for(int j = 0; j < matrix[0].size(); j++){
                if(matrix[i][j] == str[0])
                    if(dfs(matrix, str, 0, i, j))
                        return true;
            }
        }
        return false;
    }
};