矩阵中的路径（Java实现）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了矩阵中的路径（Java实现），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1536字，纯文字阅读大概需要3分钟。

内容图文

public class E12FindPath {
    //与C语言不同，此处用全局静态变量用作递归中比较字符的指针
    private static int pathLength = 0;

    public static boolean hasPath(char[] matrix, int rows, int cols, char[] str){
        if(matrix == null || str == null || rows < 1 || cols < 1)
            return false;

        //布尔数组用于标记矩阵元素是否已被访问
        boolean[] visited = new boolean[rows * cols];
        for (boolean bool : visited)
            bool = false;

        for (int row = 0; row < rows; row++){
            for (int col = 0; col < cols; col++){
                //每次都重置指针
                pathLength = 0;
                if (hasPathCore(matrix, rows, cols, str,
                        row, col,visited))
                    return true;
            }
        }
        return false;
    }

    private static boolean hasPathCore(char[] matrix, int rows, int cols, char[] str,
                                int row, int col, boolean[] visited){
        //递归终止条件
        if (str.length == pathLength)
            return true;

        boolean hasPath = false;
        if (row >= 0 && row < rows && col >= 0 && col < cols
                && !visited[row * cols + col] && matrix[row * cols + col] == str[pathLength]){
            pathLength++;
            visited[row * cols + col] = true;
            //易犯错误，采用row++，将会改变row本身的值
            hasPath = hasPathCore(matrix, rows, cols, str,
                    row + 1, col, visited) ||
                    hasPathCore(matrix, rows, cols, str, row - 1, col, visited) ||
                    hasPathCore(matrix, rows, cols, str, row, col + 1, visited) ||
                    hasPathCore(matrix, rows, cols, str, row, col - 1, visited);
            //此路径不符合则回溯
            if (!hasPath){
                pathLength--;
                visited[row * cols + col] = false;
            }
        }
        return hasPath;
    }

    //测试用例
    public static void main(String[] args){
        char[] matrix = {'a', 'b', 'c', 'd', 'e', 'f'};
        char[] str = {'b', 'e', 'd'};
        System.out.println(E12FindPath.hasPath(matrix, 2, 3, str));

    }
}

内容总结

以上是互联网集市为您收集整理的矩阵中的路径（Java实现）全部内容，希望文章能够帮你解决矩阵中的路径（Java实现）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端