矩阵中的路径问题
矩阵中的路径
http://www.nowcoder.com/questionTerminal/c61c6999eecb4b8f88a98f66b273a3cc
public static boolean hasPath(char[] matrix, int rows, int cols, char[] str){
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
//row*cols+col表示在矩阵中的位置
//每次都需要重置isVisited
boolean[] isVisited = new boolean[rows*cols+cols];
//只要有一次成功,立即返回
if (visited(matrix,rows,cols,str,isVisited,i,j,0)){
return true;
}
}
}
return false;
}
public static boolean visited(char[] matrix, int rows, int cols, char[] str, boolean[] isVisited,int row,int col,int index){
//判断str已经遍历完,返回成功
if (index >= str.length){
return true;
}
//如果row和col越界,如果已经访问过当前结点,如果和当前结点的字符不相等,返回false
if (row < 0 || row >= rows || col < 0 || col >= cols || isVisited[row*cols+col] == true || matrix[row*cols+col] != str[index]){
return false;
}
//否则将当前结点设置为已访问
//匹配下一个字符
isVisited[row*cols+col] = true;
index++;
//依次向下,向右,向上,向左递归匹配
return visited(matrix,rows,cols,str,isVisited,row+1,col,index) ||//向下
visited(matrix,rows,cols,str,isVisited,row,col+1,index) ||//向右
visited(matrix,rows,cols,str,isVisited,row-1,col,index) ||//向上
visited(matrix,rows,cols,str,isVisited,row,col-1,index);//向左
}