class Solution {
public:
    bool hasPath(vector<vector<char>>& matrix, string &str) {
        for(int i = 0; i < matrix.size(); i ++){
            for(int j = 0; j < matrix[i].size(); j ++){
                if(dfs(matrix,str,0,i,j)) return true;
            }
        }
        return false;
    }
    bool dfs(vector<vector<char>>& matrix, string& str,int u,int i,int j){
        if(i < 0 || i >= matrix.size() || j < 0 || j >= matrix[i].size()) return false;
        if(matrix[i][j] != str[u]) return false;
        if(u == str.length() - 1) return true;
        if(matrix[i][j] == '*') return false;
        char t = matrix[i][j];
        matrix[i][j] = '*';
        int ud[4] = {0,0,-1,1};
        int lr[4] = {1,-1,0,0};
        for(int k = 0; k < 4; k ++){
            if(dfs(matrix,str,u + 1, i + ud[k],j + lr[k])) return true;
        }
        matrix[i][j] = t;
        return false;
    }
};