class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param matrix string字符串 
     * @param rows int整型 
     * @param cols int整型 
     * @param str string字符串 
     * @return bool布尔型
     */
    int m,n,visit[1000][1000],ll;
    char mmap[1000][1000];
    string tempstr;
    string sstr;
    int flag = 0;
    void dfs(int x,int y,int l){
       if(x=m||y=n||l>=ll){
           return;
       }
        if(!visit[x][y]){
            visit[x][y] = 1;
            tempstr += mmap[x][y];
            if(tempstr[l] == sstr[l]){//依次比较每一位,不同就停止
                if(tempstr == sstr){
                    flag = 1;
                    return ;
                }
                l++;
                dfs(x,y+1,l);
                dfs(x+1,y,l);
                dfs(x,y-1,l);
                dfs(x-1,y,l);
            }
            tempstr.pop_back();;
            visit[x][y] = 0;
        }
       return ;
    }
    bool hasPath(string matrix, int rows, int cols, string str) {
        // write code here
        int k = 0;
        ll =  str.length();
        int len = matrix.length();
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                mmap[i][j] = matrix[k++];//把字符地图做好
            }
        }
        memset(visit,0,sizeof(visit));
        m = rows;
        n = cols;
        tempstr = "";
        sstr = str;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                dfs(i,j,0);//地图上的每个点作为起点,去找路径。
                if(flag==1)
                    return true;
                tempstr = "";
                memset(visit,0,sizeof(visit));
            }
        }
        return false;
    }
};