C++ 代码

class Solution{

public:
vector<vector<char>> m;
int vis[1001][1001];
bool dfs(int step,int len,string str,string pat,int x,int y){
    if (step == len-1){
        return true;
    }
    if (x-1>=0 && m[x-1][y] == str[step+1] && (!vis[x-1][y])){
        vis[x-1][y] = 1; 
        pat.push_back(m[x-1][y]);
        if (dfs(step+1,len,str,pat,x-1,y)) 
            return true;
        pat.pop_back();
        vis[x-1][y] = 0;
    }
    if (x+1<m.size() && m[x+1][y] == str[step+1] && (!vis[x+1][y]) ){
        vis[x+1][y] = 1; 
        pat.push_back(m[x+1][y]);
        if (dfs(step+1,len,str,pat,x+1,y)) 
            return true;
        pat.pop_back();
        vis[x+1][y] = 0;
    }
    if (y-1>=0 && m[x][y-1] == str[step+1] && !vis[x][y-1] ){
        vis[x][y] = 1; 
        pat.push_back(m[x][y-1]);
        if (dfs(step+1,len,str,pat,x,y-1)) 
            return true;
        pat.pop_back();
        vis[x][y-1] = 0;
    }
    if (y+1<m[0].size() && m[x][y+1] == str[step+1] && !vis[x][y+1]){
        vis[x][y+1] = 1; 
        pat.push_back(m[x][y+1]);
        if (dfs(step+1,len,str,pat,x,y+1)) 
            return true;
        pat.pop_back();
        vis[x][y+1] = 0;
    }
    return false;

}
bool hasPath(vector<vector<char>>& matrix, string str) {
    m = matrix;
    string pat = "";
    memset(vis,0,sizeof(vis));
    for (int i=0;i<matrix.size();i++){
        for(int j=0;j<matrix[0].size();j++){
            if (matrix[i][j] == str[0]){
                vis[i][j] = 1;
                pat.push_back(matrix[i][j]);
                if (dfs(0,str.size(),str,pat,i,j)) return true;
                pat.pop_back();
                vis[i][j] = 0;
            }
        }
    }
    return false;
}

};