矩阵中的路径问题

矩阵中的路径

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);//向左
}
全部评论

相关推荐

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