回溯法

在解决算法问题时，我们的第一个想法可能就是暴力法，比如暴力枚举所有可能的结果，但是暴力法的效率太低了，有时候达不到我们的要求。在这里我们介绍一种比暴力法稍微高级一点的算法，回溯法。回溯法是在多个可能的分支中选择一支，如果满足条件则继续查找，如果不满足结果，则回溯到上一个节点。

假如我们有下图所示结构

我们想在该树形结构中找到 "abc" 的路径，过程如下所示

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

这是一个可以使用回溯法解决的问题。首先判断矩阵的某个位置是否为字符串的第 个字符，如果是继续向四周查找第 个字符，并以此类推，直到找到最后一个字符；如果不是第 个字符，则回溯到上一个位置去查找第 个字符。因为已经经过了的路径不能重复经过，所以我们使用一个布尔矩阵 visited 来表示是否访问过矩阵中的某个位置。代码如下：

public class Path {
    // matrix：字符矩阵
    // str：要查找的字符串
    public static boolean hasPath(char[][] matrix, char[] str) {
        // 对输入参数合法性的判断
        if (matrix == null || matrix.length < 1 || matrix[0].length < 1) {
            return false;
        }
        // 获得矩阵的行数和列数
        int rows = matrix.length;
        int columns = matrix[0].length;
        // 定义一个布尔矩阵，用以确定矩阵某个元素已经被访问过
        boolean[][] vistied = new boolean[rows][columns];
        // 初始化布尔矩阵
        for (int row = 0; row < rows; row++) {
            for (int column = 0; column < columns; column++) {
                vistied[row][column] = false;
            }
        }
        // pathLength表示以匹配的字符串的长度
        int pathLength = 0;
        // 遍历矩阵进行匹配
        for (int row = 0; row < rows; row++) {
            for (int column = 0; column < columns; column++) {
                if (hasPathCore(matrix, row, column, str, pathLength, vistied)) {
                    return true;
                }
            }
        }
        return false;
    }
    // 判断位置 (row, column) 是否有第 pathLength 个字符后的路径
    public static boolean hasPathCore(char[][] martix, int row, int column, char[] str, int pathLength, boolean[][] visited) {
        // pathLength 表示以匹配的字符的个数，如果个数大于等于(其实这里等于就可以)字符串的长度，则匹配成功
        if (pathLength >= str.length) {
            return true;
        }
        // 后续是否匹配
        boolean hasPath = false;
        // 如果该位置匹配，且该位置在矩阵内
        if (row >= 0 && row < martix.length && column >= 0 && column < martix[0].length && martix[row][column] == str[pathLength] && !visited[row][column]) {
            // 匹配长度+1
            pathLength++;
            // 设置为已访问
            visited[row][column] = true;
            // 在四周进行匹配
            hasPath = hasPathCore(martix, row, column - 1, str, pathLength, visited)
                    || hasPathCore(martix, row - 1, column, str, pathLength, visited)
                    || hasPathCore(martix, row + 1, column, str, pathLength, visited)
                    || hasPathCore(martix, row, column + 1, str, pathLength, visited);
            // 如果四周的路径都不匹配，进行回溯，匹配的长度和已访问设置为false
            if (!hasPath) {
                pathLength--;
                visited[row][column] = false;
            }
        }
        return hasPath;
    }
    public static void main(String[] args) {
        char[][] matrix = {
                {'a', 'b', 't', 'g'},
                {'c', 'f', 'c', 's'},
                {'j', 'd', 'e', 'h'}
        };
        char[] str = {'t', 'c', 'f', 'd', 'j'};
        System.out.println(hasPath(matrix, str));  // true
    }
}

题目：地上有一个 行 列的方格。一个机器人从坐标 #card=math&code=%280%2C%200%29&height=20&width=37) 的格子开始移动，它每次可以向左、右、上、下移动一格，但不能进入行坐标和列坐标的数位之和大于 的格子。例如当 为 时，机器人能进入 #card=math&code=%2835%2C%2037%29&height=20&width=53)，因为 。但它不能进入方格 #card=math&code=%2835%2C%2038%29&height=20&width=53)，因为 。请问该机器人能够到达多少个格子?

这道题目和上道题很相似，同样可以使用回溯法进行解决。当机器人进入 的格子时，判断它是否能进入，如果能进入，则继续判断相邻的四个格子是否能进入。同理，我们也会用一个布尔矩阵来标记是否访问过该矩阵，以防重复统计，完整代码如下：

public class RobotCount {
    // threshold：阈值，即题目中的 k 值
    // rows, columns 矩阵的行数和列数
    public static int movingCount(int threshold, int rows, int columns) {
        // 输入参数合法性验证
        if (threshold <= 0 || rows <= 0 || columns <= 0) {
            return 0;
        }
        // 布尔矩阵
        boolean[][] visited = new boolean[rows][columns];
        // 布尔矩阵初始化
        for (int row = 0; row < rows; row++) {
            for (int column = 0; column < columns; column++) {
                visited[row][column] = false;
            }
        }
        // 从坐标 (0, 0) 开始移动
        return movingCountCore(threshold, rows, columns, 0, 0, visited);
    }
    // 从坐标 (row, column) 开始移动能够访问的格子数
    private static int movingCountCore(int threshold, int rows, int columns, int row, int column, boolean[][] visited) {
        int count = 0;
        // 如果能进入坐标 (row, column)
        if (check(threshold, rows, columns, row, column, visited)) {
            // 标记以访问
            visited[row][column] = true;
            // 进入相邻的四个格子
            count = 1 + movingCountCore(threshold, rows, columns, row - 1, column, visited)
                    + movingCountCore(threshold, rows, columns, row, column - 1, visited)
                    + movingCountCore(threshold, rows, columns, row + 1, column, visited)
                    + movingCountCore(threshold, rows, columns, row, column + 1, visited);
        }
        return count;
    }
    // 判断是否能进入坐标 (row, column)
    private static boolean check(int threshold, int rows, int columns, int row, int column, boolean[][] visited) {
        if (row >= 0 && row < rows
                && column >= 0 && column < columns
                && (getDigitalNumber(row) + getDigitalNumber(column)) <= threshold
                && !visited[row][column]) {
            return true;
        }
        return false;
    }
    // 获得数字 n 的数位和
    private static int getDigitalNumber(int number) {
        int sum = 0;
        while (number > 0) {
            sum += number % 10;
            number = number / 10;
        }
        return sum;
    }
    public static void main(String[] args) {
        System.out.println(movingCount(10, 100, 100)); // 309
    }
}

总结：

• 通常在二维矩阵中查找路径这类问题都可以使用回溯法解决。
• 通常物体或人在二维方格运动这类问题都可以使用回溯法解决。