剑指offer-65-矩阵路径

矩阵中的路径

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

思路

dfs递归
参考了官方题解,官方给了dfs的模板,值得一看。
递归:先写终止条件,再写实现体。

代码

public class Solution {
    char[] mat;
    int h;
    int w;
    int[] dire=new int[]{-1,0,1,0,-1};
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {   if(str==null||str.length<=0){return false;}
        mat=matrix;
        h=rows;
        w=cols;
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                if(dfs(i,j,0,str)){
                    return true;
                }
            }
        }
        return false;
    }
    public boolean dfs(int i,int j,int pos,char[] str){
        if(i<0||i>=h||j<0||j>=w){return false;}
        char ch=mat[i*w+j];
        //判断是否访问或不等位置不匹配
        if(ch=='#'||ch!=str[pos]){
            return false;
        }
        //判断是否匹配到最后一个字符
        if(pos==str.length-1){
            return true;
        }
        mat[i*w+j]='#';
        boolean f=false;
        for(int k=0;k<4;k++){
            if(dfs(i+dire[k],j+dire[k+1],pos+1,str)){
                return true;
            }
        }
        mat[i*w+j]=ch;
        return false;
    }
}
剑指offer与数据结构 文章被收录于专栏

本专栏包括剑指offer题目和一些刷题用的数据结构,单调栈,树状数组,差分数组,后面还会更新红黑树等较为复杂的数据结构

全部评论

相关推荐

09-23 14:45
贵州大学 财务
勇敢求职牛牛:怎么9.2佬人手一个中信证券实习
点赞 评论 收藏
分享
10-16 15:48
算法工程师
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务