机器人的运动范围

题目：

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

思考：

提示

• 采用 DFS 递归，根据行列数创建 boolean 类型二维数组，哪个访问过了就将其值改为 true

• 所以不可能情况：

  1. 行列索引越界

  2. 数组值为 true

  3. 数位之和大于 k

• bitSum() 为计算数位之和函数

题解：

class Solution {

    public int movingCount(int m, int n, int k) {

        boolean[][] visited = new boolean[m][n];

        return dfs(visited, m, n, k, 0, 0);
    }

    private int dfs(boolean[][] visited, int m, int n, int k, int i, int j) {

        if(i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || bitSum(i) + bitSum(j) > k) return 0;

        visited[i][j] = true;

        return 1 + dfs(visited, m, n, k, i + 1, j) + dfs(visited, m, n, k, i, j + 1) +

                   dfs(visited, m, n, k, i - 1, j) + dfs(visited, m, n, k, i, j - 1);
    }

    private int bitSum(int n) {
        int sum = 0;
        while(n > 0) {
            sum += n % 10;
            n /= 10;
        }
        return sum;
    }
}