图的遍历，回溯

题目链接-来源：力扣（LeetCode）

地上有一个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

思路：

依然是图的遍历问题，考虑 DFS 和 BFS 两种方案。BFS由于需要建立队列，实现起来会麻烦一些，我们考虑DFS。
同前一题 矩阵中的路径 一样，本题需要考虑机器人下一步行进的 可能的位置 （数组下标不越界，并且下标之和不能大于k）。由于我们是从[0,0]点开始进行的，所以行进方向只需向下或向右即可，对于遍历过的方格，用一个全局二维数组 reahced[][] 记录是否访问过。DFS每到达新的一格就给全局变量 res++ （当然你也可以像我一样直接用返回值记录访问的格子数）当没有可选方向时直接返回即可。

时间复杂度：O(mn)
空间复杂度：O(mn)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public int movingCount(int m, int n, int k) {
        int[][] reached = new int[m][n];
        return reach(reached, 0, 0, k);
    }
    
    private int reach(int[][] reached, int i, int j, int k) {
        int m = reached.length;
        int n = reached[0].length;
        if(i >= m || j >= n || reached[i][j] == 1 || j < 0 || i < 0) {
            return 0;
        }
        
        int digitSum = 0;
        int y = i, x = j;
        while (y > 0) {
            digitSum += y % 10;
            y /= 10;
        }
        while (x > 0) {
            digitSum += x % 10;
            x /= 10;
        }
        if (digitSum > k) {
            return 0;
        }
        
        reached[i][j] = 1;
        int[] dy = { 0, 1}, dx = {1, 0};
        int sum = 1;
        for (int l = 0; l < 2; l++) {
            sum += reach(reached, i + dy[l], j + dx[l], k);
        }
        return sum;
    }
}