【剑指12】矩阵中的路径

题目描述

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子

分析

public class Solution12{
    public static void main(String[] args) {
        char[] matrix = {'a', 'b', 'c', 'e', 's', 'f', 'c', 's', 'a', 'd', 'e', 'e'};
        char[] str = {'b', 'c', 'c', 'e', 'd'};
        System.out.println(hasPath(matrix, 3, 4, str)); //true
        char[] str2 = {'a', 'b', 'c', 'd'};
        System.out.println(hasPath(matrix, 3, 4, str2)); //false
    }

    public static boolean hasPath(char[] matrix, int rows, int columns, char[] str) {
        //校验参数
        if (matrix == null || matrix.length == 0 || rows < 0 || columns < 0 || str == null || str.length == 0 || rows * columns != matrix.length || rows * columns < str.length) {
            return false;
        }

        boolean[] visited = new boolean[rows * columns];
        int len = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (coreHasPath(matrix, rows, columns, str, i, j, visited, len)) return true;
            }
        }
        return false;
    }

    public static boolean coreHasPath(char[] matrix, int rows, int columns, char[] str, int row, int column, boolean[] visited, int len) {
        boolean flag = false;
        if (row >= 0 && row < rows && column >= 0 && column < columns && !visited[row * columns + column] && matrix[row * columns + column] == str[len]) {
            len++;
            visited[row * columns + column] = true;
            if (len == str.length) return true;
            flag = coreHasPath(matrix, rows, columns, str, row, column + 1, visited, len) ||
                    coreHasPath(matrix, rows, columns, str, row, column - 1, visited, len) ||
                    coreHasPath(matrix, rows, columns, str, row - 1, column, visited, len) ||
                    coreHasPath(matrix, rows, columns, str, row + 1, column, visited, len);
            if (!flag) {
                len--;
                visited[row * columns + column] = false;
            }
        }

        return flag;
    }
}