关于java:JZ065矩阵中的路径

34次阅读

共计 1995 个字符，预计需要花费 5 分钟才能阅读完成。

请设计一个函数，用来判断在一个矩阵中是否存在一条蕴含某字符串所有字符的门路。门路能够从矩阵中的任意一个格子开始，每一步能够在矩阵中向左，向右，向上，向下挪动一个格子。如果一条门路通过了矩阵中的某一个格子，则该门路不能再进入该格子。例如

a b c e

s f c s

a d e e

矩阵中蕴含一条字符串 ”bcced” 的门路，然而矩阵中不蕴含 ”abcb” 门路，因为字符串的第一个字符 b 占据了矩阵中的第一行第二个格子之后，门路不能再次进入该格子。

题目链接 : 矩阵中的门路

/**
 * 题目：矩阵中的门路
 * 题目形容
 * 请设计一个函数，用来判断在一个矩阵中是否存在一条蕴含某字符串所有字符的门路。门路能够从矩阵中的任意一个格子开始，每一步能够在矩阵中
 * 向左，向右，向上，向下挪动一个格子。如果一条门路通过了矩阵中的某一个格子，则该门路不能再进入该格子。例如
 * a b c e
 * s f c s
 * a d e e
 * 矩阵中蕴含一条字符串 "bcced" 的门路，然而矩阵中不蕴含 "abcb" 门路，因为字符串的第一个字符 b 占据了矩阵中的第一行第二个格子之后，门路不能
 * 再次进入该格子。* 题目链接：* https://www.nowcoder.com/practice/c61c6999eecb4b8f88a98f66b273a3cc?tpId=13&&tqId=11218&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
 */
public class Jz65 {private final static int[][] next = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
    private int rows;
    private int cols;

    /**
     * 回溯法
     *
     * @param matrix
     * @param rows
     * @param cols
     * @param str
     * @return
     */
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {if (rows == 0 || cols == 0) {return false;}
        this.rows = rows;
        this.cols = cols;
        boolean[][] marked = new boolean[rows][cols];
        char[][] array = buildMatrix(matrix);
        for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {if (backtracking(array, str, marked, 0, i, j)) {return true;}
            }
        }
        return false;
    }

    private boolean backtracking(char[][] matrix, char[] str, boolean[][] marked, int pathLen, int r, int c) {if (pathLen == str.length) {return true;}

        if (r < 0 || r >= rows || c < 0 || c >= cols || matrix[r] != str[pathLen] || marked[r]) {return false;}

        marked[r] = true;
        for (int[] n : next) {if (backtracking(matrix, str, marked, pathLen + 1, r + n[0], c + n[1])) {return true;}
        }
        marked[r] = false;
        return false;
    }

    private char[][] buildMatrix(char[] array) {char[][] matrix = new char[rows][cols];
        for (int r = 0, idx = 0; r < rows; r++) {for (int c = 0; c < cols; c++) {matrix[r] = array[idx++];
            }
        }
        return matrix;
    }

    public static void main(String[] args) {Jz65 jz65 = new Jz65();
        Jz65 jz651 = new Jz65();
        char[] array = "abcesfcsadee".toCharArray();
        char[] array2 = "abcesfcsadee".toCharArray();
        boolean result1 = jz65.hasPath(array, 3, 4, "bcced".toCharArray());
        boolean result2 = jz651.hasPath(array2, 3, 4, "abcb".toCharArray());
        System.out.println(result1);
        System.out.println(result2);
    }
}