矩阵中的路径

回溯剪枝，只在和目标串能一位一位对应上的字符上做DFS，如果全对应上了，即 depth == str.lenght ，则说明存在一条这样的路径，返回true。

    public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        if (matrix == null && str == null) return true;
        if (str == null) return true;
        if (matrix == null) return false;
        int mLen = matrix.length, sLen = str.length;
        if (mLen == 0 && sLen == 0) return true;
        if (sLen > mLen) return false;
        boolean[] isVisit = new boolean[mLen];
        for (int i = 0; i < mLen; i++) {
            if (matrix[i] == str[0]) {
                isVisit[i] = true;
                if (hasPath(matrix, cols, str, 1, i, isVisit)) {
                    return true;
                }
                isVisit[i] = false;
            }
        }
        return false;
    }

public boolean hasPath(char[] matrix, int cols, char[] str, int depth, int pre, boolean[] isVisit) {
    if (depth == str.length) {
        return true;
    }
    boolean res = false;
    for (int i = 0; i < matrix.length; i++) {
        if (isVisit[i] || !isAdjoin(pre, cols, matrix.length, i)) {
            continue;
        }
        if (str[depth] != matrix[i]) {
            continue;
        } else {
            isVisit[i] = true;
            res = hasPath(matrix, cols, str, depth + 1, i, isVisit);
            if (res) return res;
            isVisit[i] = false;
        }
    }
    return res;
}

public boolean isAdjoin(int pre, int cols, int lenght, int i) {
    if (pre - cols >= 0 && pre - cols == i) return true;
    if (pre + cols < lenght && pre + cols == i) return true;
    if (pre % cols == 0 && pre + 1 == i) return true;
    if (pre % cols == cols - 1 && pre - 1 == i) return true;
    if ((pre % cols > 0 && pre % cols < cols - 1) && (pre + 1 == i || pre - 1 == i)) return true;
    return false;
}