剑指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题目和一些刷题用的数据结构,单调栈,树状数组,差分数组,后面还会更新红黑树等较为复杂的数据结构