矩阵中的路径

矩阵中的路径

http://www.nowcoder.com/questionTerminal/c61c6999eecb4b8f88a98f66b273a3cc

【回溯法】 与力扣79题同理

class Solution {
public:
    int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
    int n,m;
    int len;
    bool f[10100];
    bool dfs(char* matrix, int x, int y, char* str, int l)
    {
        if(x<0||x>n-1||y<0||y>m-1||f[x*m+y]||matrix[x*m+y]!=str[l]) return false;
        if(l==len-1) return true;
        f[x*m+y]=true;
        for(int i=0;i<4;i++)
        {
            int dx=x+dir[i][0];
            int dy=y+dir[i][1];
            if(dfs(matrix,dx,dy,str,l+1)) return true;
        }
        f[x*m+y]=false;
        return false;
    }
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        n=rows;
        m=cols;
        len=strlen(str);
        memset(f,false,sizeof(f));
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(dfs(matrix,i,j,str,0)) return true;
            }
        }
        return false;
    }
};
全部评论

相关推荐

4 收藏 评论
分享
牛客网
牛客企业服务