回溯法之矩阵中的路径和机器人的运动范围

1. 回溯法

回溯法解决非常适合有多个步骤组成的问题，并且每个步骤都有多个选项。用回溯法解决的问题的所有选项可以形象地用树状结构表示。如果再叶节点的状态不满足约束条件。那么只好回溯它的上一个节点再尝试其他的选项。

1.1 矩阵中的路径

public class Solution1 { public boolean hasPath(char[] matrix, int rows, int cols, char[] str) { //标志位，初始化为false boolean[] flag = new boolean[matrix.length]; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (judge(matrix, i, j, rows, cols, flag, str, 0)) { return true; } } } return false; } private boolean judge(char[] matrix, int i, int j, int rows, int cols, boolean[] flag, char[] str, int k) { //先根据i和j计算匹配的第一个元素转为一维数组的位置 int index = i * cols + j; //递归终止条件 if (i < 0 || j < 0 || i >= rows || j >= cols || matrix[index] != str[k] || flag[index] == true) return false; //若k已经到达str末尾了，说明之前的都已经匹配成功了，直接返回true即可 if (k == str.length - 1) return true; //要走的第一个位置置为true，表示已经走过了 flag[index] = true; //回溯，递归寻找，每次找到了就给k加一，找不到，还原 if (judge(matrix, i - 1, j, rows, cols, flag, str, k + 1) || judge(matrix, i + 1, j, rows, cols, flag, str, k + 1) || judge(matrix, i, j - 1, rows, cols, flag, str, k + 1) || judge(matrix, i, j + 1, rows, cols, flag, str, k + 1)) { return true; } //走到这，说明这一条路不通，还原，再试其他的路径 flag[index] = false; return false; } public static void main(String[] args) { char[] matrix = {'a', 'b', 't', 'g', 'c', 'f', 'c', 's', 'j', 'd', 'e', 'h'}; char[] str = {'b', 'f', 'c', 'e'}; Solution1 solution1 = new Solution1(); System.out.println(solution1.hasPath(matrix, 3, 4, str)); } }

1.2 机器人的运动范围

public class Solution2 { public int movingCount(int threshold, int rows, int cols) { if (threshold < 0 || rows <= 0 || cols <= 0) { return 0; } boolean[][] isVisit = new boolean[rows][cols]; int count = movingCountCore(threshold, rows, cols, 0, 0, isVisit); return count; } private int movingCountCore(int threshold, int rows, int cols, int row, int col, boolean[][] isVisit) { if (row < 0 || col < 0 || row >= rows || col >= cols || isVisit[row][col] || cal(col) + cal(row) > threshold) { return 0; } isVisit[row][col] = true; return 1 + movingCountCore(threshold, rows, cols, row - 1, col, isVisit) + movingCountCore(threshold, rows, cols, row + 1, col, isVisit) + movingCountCore(threshold, rows, cols, row, col - 1, isVisit) + movingCountCore(threshold, rows, cols, row, col + 1, isVisit); } private int cal(int num) { int sum = 0; while (num > 0) { sum += num % 10; num /= 10; } return sum; } public static void main(String[] args) { Solution2 solution2 = new Solution2(); System.out.println(solution2.movingCount(-5, 18, 18)); } }