《剑指offer第二版》面试题12：矩阵中的路径（java）

题目描述

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某个字符串所有字符的路径。路径可以从矩阵中的任何一格开始，每一步可以在矩阵中向上、下、左、右移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面3*4的矩阵中包含一条字符串"bfce"的路径，但不包含"abfb"的路径。

a b t g
c f c s
j d e h

解题思路:

1. 假设路径为A，长度为n。
2. 假设矩阵中的某条路径，满足A的前i-1个字符，则在矩阵当前节点的上、下、左、右寻找路径A的第i个字符，如果找到第i个字符，就继续循环。如果没找到，则返回矩阵中路径的上一个字符，重新寻找第n-1个字符。
3. 由于路径不能重复进入矩阵的格子，所以还需定义一个和字符矩阵相同大小的布尔矩阵，用于标识路径是否进入了某个格子。

代码

static class PathLength{
    int length;
}

boolean hasPath(char[][] matrix, String path){
    if (matrix == null) {
        return false;
    }
    if (path == null || path.length() <= 0) {
        return true;
    }
    boolean[][] visted = new boolean[matrix.length][matrix[0].length];
    PathLength pathLength = new PathLength();
    pathLength.length = 0;

    for(int i = 0; i < matrix.length; i ++) {
        for (int j = 0; j < matrix[0].length; j++) {
            if (hasPathCore(matrix, path, pathLength, i, j, visted)) {
                return true;
            }
        }
    }
    return false;
}

boolean hasPathCore(char[][] matrix, String path, PathLength pathLength, int row, int colum, boolean[][] visted){
    if (path.length() == pathLength.length) {
        // 已达到路径的末尾，说明找到了
        return true;
    }
    boolean hasPath = false;
    if (row >= 0
            && row < matrix.length
            && colum >= 0
            && colum < matrix[0].length
            && matrix[row][colum] == path.charAt(pathLength.length)
            && !visted[row][colum]
        ) {
        // matrix[row][colum] 和需要找的路径的节点相同
        visted[row][colum] = true;
        pathLength.length ++;
        // 继续判断[row][colum]的上、下、左、右节点是否和路径的下个节点相同
        hasPath = hasPathCore(matrix, path, pathLength, row + 1, colum, visted)
            || hasPathCore(matrix, path, pathLength, row - 1, colum, visted)
            || hasPathCore(matrix, path, pathLength, row, colum + 1, visted)
            || hasPathCore(matrix, path, pathLength, row, colum - 1, visted);

        if (!hasPath) {
            // 没找到路径，还原变量，重新回到上个节点
            pathLength.length --;
            visted[row][colum] = false;
        }
    }
    return hasPath;
}