剑指 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 <= 100
0 <= k <= 20

算法思路：

本题与矩阵中的路径类似，是典型的矩阵搜索问题，此类问题通常使用 DFS或BFS解决，此题还有2个优化的地方，分别是 数位之和计算 和 搜索方向简化

数位之和计算

依题意，x -> x+1 的时候数位之和的增量要分类计算

如果（x+1)%10 = 0 那么 s(x+1) = s(x) - 8
反之，那么s(x+1) = s(x) + 1

那么就有三元表达式写法

(x + 1) % 10 != 0 ? s_x + 1 : s_x - 8

搜索方向简化

我们在搜索的过程中搜索方向可以缩减为向右和向下，而不必再向上和向左进行搜索。

如下图，我们展示了 16 * 16 的地图随着限制条件 k 的放大，可行方格的变化趋势，每个格子里的值为行坐标和列坐标的数位之和，蓝色方格代表非障碍方格，即其值小于等于当前的限制条件 k。我们可以发现随着限制条件 k 的增大，(0, 0) 所在的蓝色方格区域内新加入的非障碍方格都可以由上方或左方的格子移动一步得到。而其他不连通的蓝色方格区域会随着 k 的增大而连通，且连通的时候也是由上方或左方的格子移动一步得到，因此我们可以将我们的搜索方向缩减为向右或向下。

深度优先遍历DFS

算法解析：

递归参数：当前元素在矩阵中的行列索引 i,j，两者的数位和 s1,s2
终止条件：当行列索引不符合要求或当前元素已经访问过（使用visit数组判断是否遍历），返回0，代表不计入可达解
递推工作
- 标记当前单元格，将索引 i,j存入visit中，代表已经被访问过
- 搜索下一单元格，计算当前元素的 下，右 两个方向元素的数位和，并开启下层递归
- 回溯返回值：返回 1 + 右方搜索的可达解总数 + 下方搜索的可达解总数，代表从本单元格递归搜索的可达解总数

AC代码

class Solution {
    int m, n, k;
    boolean[][] visited;
    public int movingCount(int m, int n, int k) {
        this.m = m; this.n = n; this.k = k;
        this.visited = new boolean[m][n];
        return dfs(0, 0, 0, 0);
    }
    public int dfs(int i, int j, int si, int sj) {
        if(i >= m || j >= n || k < si + sj || visited[i][j]) return 0;
        visited[i][j] = true;
        return 1 + dfs(i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj) + dfs(i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8);
    }
}