矩阵中的路径

题目链接：https://www.nowcoder.com/practice/c61c6999eecb4b8f88a98f66b273a3cc?tpId=13&&tqId=11218&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

代码：

class Solution {
public:
    char* a=0;
    int len=0,h=0,w=0;
    int go[4][2]={0,1,0,-1,1,0,-1,0};
    bool dfs(int x,int y,int pos,char* str)
    {
        if(x<0||x>=h||y<0||y>=w) return 0;
        char s=a[x*w+y];
        if(s!=str[pos]||s=='#') return 0;
        if(pos+1==len) return 1;
        a[x*w+y]='#';
        for(int i=0;i<4;i++)
        {
            int xx=x+go[i][0],yy=y+go[i][1];
            if(dfs(xx,yy, pos+1, str))return 1;
        }
        a[x*w+y]=s;
        return 0;
    }
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        a=matrix;
        h=rows,w=cols;
        len=strlen(str);
        for(int i=0;i<h;i++)
            for(int j=0;j<w;j++)
            {
                if(dfs(i,j,0,str)) return 1;
            }
        return 0;
    }


};

 

本文地址：https://blog.csdn.net/chimchim04/article/details/107286471