参照原来答案的方法..

矩阵中的路径

http://www.nowcoder.com/questionTerminal/2a49359695a544b8939c77358d29b7e6

public boolean hasPath (char[][] matrix, String word) {
// write code here
if(matrix==null||word.length()==0)return false;
boolean[][] isPath = new boolean[matrix.length][matrix[0].length];
for(int i = 0;i<matrix.length;i++){
for(int j =0;j<matrix[0].length;j++){
if(helper(i,j,matrix,isPath,0,word))
return true;
}
}
return false;
}
public boolean helper(int i,int j,char[][] matrix,boolean[][] isPath,int cur,String word){
if(i<0||i>=matrix.length||j<0||j>=matrix[0].length||isPath[i][j]==true)
return false;
if(matrix[i][j]==word.charAt(cur)){
if(cur==word.length()-1) return true;
isPath[i][j]=true;
boolean flag = helper(i+1,j,matrix,isPath,cur+1,word);
if(flag) return true;
flag=helper(i-1,j,matrix,isPath,cur+1,word);
if(flag) return true;
flag=helper(i,j+1,matrix,isPath,cur+1,word);
if(flag) return true;
flag=helper(i,j-1,matrix,isPath,cur+1,word);
if(flag) return true;
isPath[i][j]=false;
}
return false;
}

全部评论

相关推荐

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