算法-12.矩阵中的路径

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。
[["a","b","c","e"],
["s","f","c","s"],
["a","d","e","e"]]

但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

    // 定义四个方向
    private final static int[][] next = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
    private static int rows;
    private static int cols;
    /**
     * 矩阵中的路径
     * 先找到目标字符串的第一个字符的位置，然后按这个字符的4个方向进行下一个字符的查找
     * 如果下一个字符的查找，4个方向都没有找到，则直接返回false，表示没有完整路径
     * @param board 二维字符矩阵
     * @param word
     * @return
     */
    public static boolean exist(char[][] board, String word) {
        rows = board.length;
        cols = board[0].length;
        char[] str = word.toCharArray();
        boolean[][] marked = new boolean[rows][cols];
        // 外层两个for循环先找到第一个字符的位置
        for (int i=0;i< rows;i++) {
            for (int j=0;j< cols; j++) {
                // 如果是false，就继续循环
                if (backtracking(board,str, marked, 0, i, j)) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 使用递归查找的方式遍历，如果字符串中第一个要查找的点就不存在，则
     * @param board     二维数组
     * @param str       需要查找的字符串转字符数组
     * @param marked    标记位置
     * @param pathLen   路径的长度
     * @param r         行数
     * @param c         列数
     * @return
     */
    private static boolean backtracking(char[][] board, char[] str, boolean[][] marked, int pathLen, int r, int c) {
        // 判断pathLen的长度是否已经达到了最大，因为pathLen是从0开始的，所以当达到字符串长度之后，就已经是全部找到
        if (pathLen == str.length) return true;
        // 如果r或者c不在二维数组中，如果在二维数组中，则设置marked[r][c]=true
        if (r < 0 || r >= rows || c < 0 || c >= cols ||
                board[r][c] != str[pathLen] || marked[r][c]) {
            return false;
        }
        // 做一个标记，如果当前位置已经找到了该字符，则标记，继续查找下一个，当全部递归查找完之后，取消标记
        // 这里做标记的原因，是因为可能会重复找到这个位置
        // 当再一次找到这个位置的时候，直接返回false，不进行剩下的方向的循环
        // 因为String word中可能有重复字符
        marked[r][c] = true;
        // 遍历next，按4个方向进行查找
        for (int[] n : next) {
            // 如果是false，就继续查找路径，递归查找，按4个路径找下一个字符的位置是否连续
            // 如果连续，则继续递归，直到最后一个字符找到之后，递归返回true
            if (backtracking(board, str, marked, pathLen + 1, r + n[0], c + n[1])) {
                return true;
            }
        }
        marked[r][c] = false;
        return false;
    }