矩阵中的路径

题目要求：

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

解题思路及代码实现：

1. 当矩阵中坐标为 (row, col) 的元素和路径字符串 str 中下标为 pathLength 的字符相同时，从 4 个相邻的元素 (row, col - 1) (左)、(row - 1, col) (上)、(row, col + 1) (右)、(row + 1, col) (下) 中去搜索路径字符串中下标为 pathLength + 1 的字符
2. 若 4 个相邻的元素都没有匹配字符串中下标为 pathLength + 1 的字符，则回到前一个字符 (下标为 pathLength - 1)，重新搜索
3. 重复以上过程，直到匹配路径字符串中的所有字符为止 (str.length == pathLength)

判断在一个矩阵中是否存在一条包含某字符串所有字符的路径:

    // 矩阵中左、右、上、下 的坐标变化
    private final static int[][] nextStr = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

    // 矩阵行数
    private int rows;

    // 矩阵列数
    private int cols;

/**
     *  判断在一个矩阵中是否存在一条包含某字符串所有字符的路径
     *
     * @param array  要转换为矩阵的数组
     * @param rows   矩阵行数
     * @param cols   矩阵列数
     * @param str    要查找的字符串
     * @return true or false
     */
    private boolean hasPath(char[] array, int rows, int cols, char[] str) {
        if (rows == 0 || cols == 0 || array == null) {
            return false;
        }
        this.rows = rows;
        this.cols = cols;

        boolean[][] visited = new boolean[rows][cols];
        char[][] matrix = createMatrix(array);
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (backTracking(matrix, i, j, visited, str, 0)) {
                    return true;
                }
            }
        }

        return false;
    }

回溯法搜索路径中的下一个字符:

/**
     * 回溯法搜索下一个字符
     *
     * @param matrix
     * @param row
     * @param col
     * @param visited
     * @param str
     * @param pathLength
     * @return
     */
    private boolean backTracking(char[][] matrix, int row, int col, boolean[][] visited,
                                 char[] str, int pathLength) {
        
        // 字符串 str 中的所有字符都在 matrix 中找到时返回 true
        if (pathLength == str.length) {
            return true;
        }

        if (row < 0 || row >= rows || col < 0 || col >= cols
                || matrix[row][col] != str[pathLength] || visited[row][col]) {
            return false;
        }

        visited[row][col] = true;
        for (int[] n : nextStr) { // 回溯搜索的顺序 --> 左、右、上、下 
            if (backTracking(matrix, row + n[0], col + n[1], visited, str, pathLength + 1)) {
                return true;
            }
        }

        visited[row][col] = false;
        return false;
    }

创建矩阵：

/**
     * 创建矩阵
     * @param array 矩阵中的所有字符构成的一维数组
     * @return
     */
private char[][] createMatrix(char[] array) {
        char[][] matrix = new char[rows][cols];
        for (int i = 0, index = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                matrix[i][j] = array[index++];
            }
        }
        return matrix;
    }

测试代码：

    @Test
    public void test() {
        HasPathInMatrix matrix = new HasPathInMatrix();

        char[] array = {'a', 'b', 't', 'g', 'c', 'f', 'c', 's', 'j', 'd', 'e', 'h'};

        // 矩阵中不存在路径
        char[] str = {'b', 'f', 'c', 'g'};
        boolean hasPath = matrix.hasPath(array, 3, 4, str);
        System.out.println(hasPath); // false

        // 矩阵中存在路径
        char[] str1 = {'b', 'f', 'c', 'e'};
        boolean hasPath1 = matrix.hasPath(array, 3, 4, str1);
        System.out.println(hasPath1); // true

        // 输入空指针
        char[] str4 = {'b', 'f', 'c', 'g'};
        boolean hasPath4 = matrix.hasPath(null, 3, 4, str4);
        System.out.println(hasPath4); // false

        // 矩阵只有一行,且矩阵和路径中的所有字母都相同
        char[] arr = {'z', 'j', 'c', 'z', 'y'};
        char[] str2 = {'z', 'j', 'c', 'z', 'y'};
        boolean hasPath2 = matrix.hasPath(arr, 1, 5, str2);
        System.out.println(hasPath2); // true

        // 矩阵只有一列,且矩阵和路径中的所有字母都相同
        char[] str3 = {'z', 'j', 'c', 'z', 'y'};
        boolean hasPath3 = matrix.hasPath(arr, 5, 1, str3);
        System.out.println(hasPath3); // true
    }