//矩阵路径



class Solution {
public:



    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 m=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()&&matrix[a][b]!='*')
            {
                if(dfs(matrix,str,u+1,a,b)) return true;
            }
        }
        matrix[x][y]=m;
        return false;


    }
    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;

    }


};