剑指offer-65-矩阵路径

思路

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;
    }
}