剑指offer09

题目描述

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

解题思路分析

这是很明显得回溯得问题，回溯的问题最主要的是结束条件和边界问题。
从这个题目来看这个题目的结束条件是找到了如果过包含目的字符串的路径的时候就可以结束了，或者当全部位置都遍历完了之后如果找到了，或者没找到都得结束了
然后对于边界条件就是每个点不能进行重复访问还有就是不能越界问题，所以矩阵的边界也是一个边界问题

代码实现

public static boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
    //保证的程序的鲁棒性和健壮性
    if (matrix == null || rows != cols || str == null || matrix.length <= 0 || str.length <= 0) {
        return false;
    }
    //标记该点是否被访问过，如果访问过置true，初始化都是false
    boolean[][] vis = new boolean[rows][cols];
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            //从每一个可能位置开始进行回溯，找到目的路径就可以返回
            return findPath(matrix, rows, cols, i, j, 0, vis, str);
        }
    }
}

public static boolean findPath(char[] matrix, int rows, int cols, int r, int c, int k, boolean[][] vis, char[] str) {
    //结束条件，应该很容易看懂
    if (r < 0 || r >= rows || c < 0 || c >= cols || str[k] != matrix[r * cols + c] || vis[r * cols + c]) {
        return false;
    }
    //如果当前已经匹配完了目的字符串，则可以直接返回true了
    if (k == str.length - 1) {
        return true;
    }
    //设置当前点被访问过了
    vis[r * rows + c] = true;
    //开始向上、下、左、右等方向开始进行遍历回溯
    if (findPath(matrix, rows, cols, r - 1, c, k + 1, vis, str) ||
        findPath(matrix, rows, cols, r, c - 1, k + 1, vis, str) ||
        findPath(matrix, rows, cols, r + 1, c, k + 1, vis, str) ||
        findPath(matrix, rows, cols, r, c + 1, k + 1, vis, str)) {
            return true;
    }
    //这个很重要，如果当前点向各个方向遍历都没找到对应路径的话，就应该把这个重新设置为未访问，以备下次继续访问
    vis[r * cols + c] = false;
    // 当前点各个方向下遍历和回溯都没有找到对应的路径
    return false;
}