10、剑指 Offer 13. 机器人的运动范围
一、题目
剑指 Offer 13. 机器人的运动范围 难度中等
地上有一个 m 行 n 列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当 k 为 18 时，机器人能够进入方格 [35, 37] ，因为 3+5+3+7=18 。但它不能进入方格 [35, 38]，因为 3+5+3+8=19 。请问该机器人能够到达多少个格子？
示例 1：
输入：m = 2, n = 3, k = 1
输出：3
示例 2：
输入：m = 3, n = 1, k = 0
输出：1
提示：
1 <= n,m <= 1000 <= k <= 20
二、解法
2.1、DFS + 剪枝
核心思路
如果我们将行坐标和列坐标数位之和大于 k 的格子看作障碍物，那么这道题就是一道很传统的搜索题目，我们可以使用广度优先搜索或者深度优先搜索来解决它。与 矩阵中的路径 类似，是典型的搜索 & 回溯问题。
但需要注意的是，本题不是要求找最长路径，而是可达坐标的累计数量。也就是说不需要将走过的路径恢复至未走过的状态，只需要统计走过的格子的累计数量最大值即可。
使用一个m * n大小的矩阵存储所有单元格的索引，记作 visited。借助这个访问记录矩阵，你就可以知道机器人已经走过了哪些格子，在这个过程中就可以统计走过的格子数量了。
同时这道题还有一个隐藏的优化：我们在搜索的过程中搜索方向可以缩减为向右和向下，而不必再向上和向左进行搜索。
矩阵中 满足数位和的解 构成的几何形状形如多个 等腰直角三角形 。
复杂度分析
时间复杂度：O(MN) ，最差情况下，机器人遍历矩阵所有单元格。
空间复杂度：最差情况下，visited 内存储矩阵所有单元格的索引，使用 O(MN) 的额外空间。
Code
class Solution {
// 访问记录矩阵
private int[][] visited = null;
// 参数
private int m = 0;
private int n = 0;
private int k = 0;
// 入口
public int movingCount(int m, int n, int k) {
// 初始化矩阵访问记录
visited = new int[m][n];
// 初始化参数
this.m = m;
this.n = n;
this.k = k;
// 起点坐标
int row = 0, column = 0;
return move(row, column, 0);
}
// 以 row, column 为起点移动一步
private int move(int row, int column, int max) {
// 检查 row, column 是否超限
if (row < 0 || row >= this.m || column < 0 || column >= this.n) {
return max;
}
// 检查坐标是否合法
if (checkXY(row, column, this.k) == false) {
return max;
}
// 检查该坐标是否已经走过
if (visited[row][column] != 0) {
return max;
}
max += 1;
// 写入访问记录, 防止重复访问
visited[row][column] = 1;
// 上下左右四个方向递归调用
// max = Math.max(max, move(row - 1, column, max));
max = Math.max(max, move(row + 1, column, max));
// max = Math.max(max, move(row, column - 1, max));
max = Math.max(max, move(row, column + 1, max));
return max;
}
// 检查坐标是否合法
private boolean checkXY(int x, int y, int k) {
// 边界条件
if (x < 0 || y < 0) {
return false;
}
// 计算 x y 的数位和
int sum = shuWeiSum(x) + shuWeiSum(y);
return sum > k ? false : true;
}
// 求 number 的数位和
private int shuWeiSum(int number) {
int sum = 0;
while (number != 0) {
sum += number % 10;
number /= 10;
}
return sum;
}
}
2.2、BFS
核心思路
BFS 和 DFS 两者目标都是遍历整个矩阵，不同点在于搜索顺序不同。DFS 是朝一个方向走到底，再回退，以此类推；BFS 则是按照“平推”的方式向前搜索。通常利用队列实现 BFS 。
复杂度分析
时间复杂度：O(MN) ，最差情况下，机器人遍历矩阵所有单元格，此时时间复杂度为 O(MN)。
空间复杂度：O(MN) ，最差情况下，visited 内存储矩阵所有单元格的索引，使用 O(MN) 的额外空间。
Code
class Solution {
public int movingCount(int m, int n, int k) {
// 辅助矩阵
boolean[][] visited = new boolean[m][n];
// 可达坐标累计个数
int result = 0;
// 等待访问的坐标队列
Queue<int[]> queue = new LinkedList<int[]>();
// 设置初始坐标
queue.add(new int[]{0, 0, 0, 0});
// 循环访问, 直到坐标队列为空
while (queue.size() > 0) {
// 取数
int[] tmp = queue.poll();
// 获取当前坐标行列值
int row = tmp[0], column = tmp[1];
// 检查行列坐标是否超限
if (row >= m || column >= n) {
continue;
}
// 检查坐标是否符合规则（障碍物判断）
if (checkXY(row, column, k) == false) {
continue;
}
// 检查该坐标是否已被访问过
if (visited[row][column] == true) {
continue;
}
// 标记当前坐标已经访问过
visited[row][column] = true;
// 累计可达坐标+1
result++;
// 加入下方向的坐标
queue.add(new int[]{row + 1, column});
// 加入右方向的坐标
queue.add(new int[]{row, column + 1});
}
return result;
}
// 检查坐标是否合法
private boolean checkXY(int x, int y, int k) {
// 边界条件
if (x < 0 || y < 0) {
return false;
}
// 计算 x y 的数位和
int sum = shuWeiSum(x) + shuWeiSum(y);
return sum > k ? false : true;
}
// 求 number 的数位和
private int shuWeiSum(int number) {
int sum = 0;
while (number != 0) {
sum += number % 10;
number /= 10;
}
return sum;
}
}