矩阵中的路径问题
矩阵中的路径
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);//向左 }