题目描述
代码语言：javascript复制地上有一个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。
请问该机器人能够到达多少个格子？
题目来源：https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof
示例1:
代码语言：javascript复制输入：m = 2, n = 3, k = 1
输出：3示例2:
代码语言：javascript复制输入：m = 3, n = 1, k = 0
输出：1提示：
代码语言：javascript复制1 <= n,m <= 100
0 <= k <= 20题目分析
本文与前一篇博文《剑指 offer｜12. 矩阵中的路径》，类似。
方法1：深度优先DFS
代码语言：javascript复制class Solution {
public int movingCount(int m, int n, int k) {
/**
* 二维数组，记录元素是否被已被访问
*/
boolean[][] visited = new boolean[m][n];
// 从 (0, 0) 点开始进行 dfs 操作，从上、下、左、右4个方向递归调用
return this.dsf(visited, m, n, 0, 0, k);
}
private int dsf(boolean[][] visited, int row, int col, int i, int j, int k) {
/**
* 终止条件：1、数组越界 2、数据已被访问过 3、当前字符与期望的字符不符合 4、或者访问受限（数值加起来为k）
*/
if (i < 0 || i >= row || j < 0 || j >= col || visited[i][j] || isAccessDenied(i, j, k)) {
return 0;
}
visited[i][j] = true;
return 1 dsf(visited, row, col, i 1, j, k) dsf(visited, row, col, i - 1, j, k)
dsf(visited, row, col, i, j 1, k) dsf(visited, row, col, i, j - 1, k);
}
private boolean isAccessDenied(int i, int j, int k) {
/**
* 不能进入行坐标和列坐标的数位之和大于k的格子。
* 例如，当k为18时，机器人能够进入方格 [35, 37] ，
* 因为3 5 3 7=18。但它不能进入方格 [35, 38]，因为3 5 3 8=19
*
* 另外：
* 1 <= n,m <= 100
*
* 所以下标范围为0-99，只要考虑2位数即可
*/
int sum = i / 10 i % 10 j / 10 j % 10;
return sum > k;
}
}
深度优先搜索的一个实现就完成了。但是，上述对4个方向进行遍历。但是，机器人的起点固定，访问的格子是不能重复访问的，所以，方向向右、向下2个方向就可以满足。
我们来看下，调整后是否可以。
调整后
代码语言：javascript复制class Solution {
public int movingCount(int m, int n, int k) {
/**
* 二维数组，记录元素是否被已被访问
*/
boolean[][] visited = new boolean[m][n];
// 从 (0, 0) 点开始进行 dfs 操作，从上、下、左、右4个方向递归调用
return this.dsf(visited, m, n, 0, 0, k);
}
private int dsf(boolean[][] visited, int row, int col, int i, int j, int k) {
/**
* 终止条件：1、数组越界 2、数据已被访问过 3、当前字符与期望的字符不符合 4、或者访问受限（数值加起来为k）
*/
if (i < 0 || i >= row || j < 0 || j >= col || visited[i][j] || isAccessDenied(i, j, k)) {
return 0;
}
visited[i][j] = true;
return 1 dsf(visited, row, col, i 1, j, k)
dsf(visited, row, col, i, j 1, k) ;
}
private boolean isAccessDenied(int i, int j, int k) {
/**
* 不能进入行坐标和列坐标的数位之和大于k的格子。
* 例如，当k为18时，机器人能够进入方格 [35, 37] ，
* 因为3 5 3 7=18。但它不能进入方格 [35, 38]，因为3 5 3 8=19
*
* 另外：
* 1 <= n,m <= 100
*
* 所以下标范围为0-99，只要考虑2位数即可
*/
int sum = i / 10 i % 10 j / 10 j % 10;
return sum > k;
}
}
可以看到，调整后也可以。
这样，题目剑指offer 13.机器人的运动范围，本文采用DFS 的方法给出了一个解决方法。
当然，本题也可以使用广度优先搜索BFS实现。 大家有其它的方法，也可以留言相互交流。
