机器人的运动范围
题目描述
地上有一个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。请问该机器人能够到达多少个格子？
示例：
输入：m = 2, n = 3, k = 1
输出：3
输入：m = 3, n = 1, k = 0
输出：1
提示：
1 <= n,m <= 100
0 <= k <= 20
题目分析
这题的思路和 面试题12. 矩阵中的路径 非常像，甚至比12题更加简单，都是从当前点往四个方向探索，而这题简单的地方在于不用回溯，如果行不通直接返回0就行；具体流程如下：
- 如果当前节点不符合条件，意味着当前节点阻塞，不能往下探索，所以收获为0，直接返回
- 如果当前节点符合条件，意味着从当前点开始，最少能收获1，具体的收获值为1+四个方向的收获值之和，需要注意的是，这里仍需要一个visited数组来标明哪些节点已经访问过了，不然会造成重复
- 从[ 0, 0 ]开始深度优先遍历，按照上面的流程走完，done
而在这题里计算一个数的分解结果我用一个sumOfNum数组来存放，例如142的分解结果为1+4+2=7，所以sumOfNum[142] = 7，这样可以解决重复分解（a[142][2]和a[345][142]都需要142的分解结果）；
boolean[][] visited;
int[][] direction = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int[] sumOfNum;
int m, n;
public int movingCount(int m, int n, int k) {
visited = new boolean[m][n];
this.m = m;
this.n = n;
sumOfNum = new int[m > n ? m : n];
for (int i = 0; i < sumOfNum.length; i++)
sumOfNum[i] = -1;
return canVisited(0, 0, k);
}
public int getSum(int a) {
if (sumOfNum[a] != -1)
return sumOfNum[a];
int tmp = a;
sumOfNum[a] = 0;
while (a > 0) {
sumOfNum[tmp] += (a % 10);
a /= 10;
}
return sumOfNum[tmp];
}
public int canVisited(int x, int y, int k) {
if (x < 0 || y < 0 || x == m || y == n || visited[x][y])
return 0;
if (getSum(x) + getSum(y) > k)
return 0;
visited[x][y] = true;
int sum = 1;
for (int i = 0; i < 4; i++) {
sum += canVisited(x + direction[i][0], y + direction[i][1], k);
}
return sum;
}
