class Solution {
public:
    //思路，深搜加枚举吧，小技巧，坐标可以用数组来存放时间复杂度，dfs外n^2数量级，dfs内是3^k数量级
    //k为str.size()
    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(dfs(matrix,str,0,i,j))   return true;
            }
        }
        return false;
    }

    bool dfs(vector<vector<char>> &matrix,string &str,int u,int x,int y){
        if(str[u] != matrix[x][y]) return false;
        if(u == str.size() - 1) return true;
        int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};
        //遍历各个坐标
        char t = matrix[x][y];
        matrix[x][y] = '*';
        for(int i = 0;i < 4;++i){
            int a = x + dx[i],b = y + dy[i];
            if(a >= 0 && a < matrix.size() && b >= 0 && b < matrix[a].size()){
                if(dfs(matrix,str,u + 1,a,b)) return true;
            }
        }
        matrix[x][y] = t;
        return false;
    }
};