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

对于标红的6所在位置，既可以从2和5的位置到达，又可以从7和10的位置到达，而且2和5所在位置数位和明显小于7和10所在位置数位和，所以机器人移动时，我们可以只考虑向右和向下移动就能到达所有满足条件的位置，详细的证明可以参考https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/solution/mian-shi-ti-13-ji-qi-ren-de-yun-dong-fan-wei-dfs-b/。
然后具体实现，我们可以考虑深度优先搜索，深度优先搜索本质上还是递归，所以直接上递归三部曲。

1. 递归终止条件：当机器人超过右边界和下边界，或者不满足数位和，或者已经访问过了，递归就终止了。
2. 从上一层递归获取什么：很显然，当前层如果走的通，那么可到达位置数就会加1，那么从原点走到当前位置总共有多少可到达的位置数呢，再加上从左边来的那一层，和从上面来的那一层就行了。
3. 每一层的递归返回什么：返回从原点到当前位置总共有多少可到达的位置数。

class Solution {
    boolean[][] visited;
    int m,n,k;
    public int movingCount(int m, int n, int k) {
        //初始化
        this.m=m;
        this.n=n;
        this.k=k;
        visited=new boolean[m][n];
        return dfs(0,0);
    }
    //dfs搜索可到达的位置数目
    private int dfs(int i,int j){
        if(i>=m||j>=n||cal(i)+cal(j)>k||visited[i][j]==true){
            return 0;
        }
        visited[i][j]=true;
        int count=1+dfs(i+1,j)+dfs(i,j+1);
        return count;
    }

    //计算数位和
    private int cal(int x){
        int sum=0;
        while(x!=0){
            sum+=x%10;
            x/=10;
        }
        return sum;
    }
}

优化计算数位和：

class Solution {
    boolean[][] visited;
    int m,n,k;
    public int movingCount(int m, int n, int k) {
        this.m=m;
        this.n=n;
        this.k=k;
        visited=new boolean[m][n];
        return dfs(0,0);
    }
    private int dfs(int i,int j){
        if(i>=m||j>=n||i/10+i%10+j/10+j%10>k||visited[i][j]==true){
            return 0;
        }
        visited[i][j]=true;
        int count=1+dfs(i+1,j)+dfs(i,j+1);
        return count;
    }
}

• 时间复杂度：最坏情况下，机器人需要遍历左右单元格，复杂度是O(m*n)
• 空间复杂度：最坏情况下，需要存储所有单元格的索引，所以空间复杂度为O(m*n)

DFS的思路是一条路走到底，不满足再回溯，继续找，而BFS是一层一层的往下找，同时将每一层的信息存入到一个队列，可以利用队列里存储的信息来访问下一层，在每一层的迭代中，遇到满足条件的格子，就加1

class Solution {

    public int movingCount(int m, int n, int k) {
        boolean[][] visited=new boolean[m][n];
        LinkedList<int[]> queue=new LinkedList<>();
        queue.add(new int[]{0,0});
        int res=0;
        while(!queue.isEmpty()){
            int[] grid=queue.poll();
            int x=grid[0];
            int y=grid[1];
            int sx=x/10+x%10;
            int sy=y/10+y%10;
            if(x>=m||y>=n||sx+sy>k||visited[x][y]==true){
                continue;
            }
            visited[x][y]=true;
            res++;
            queue.offer(new int[]{x+1,y});
            queue.offer(new int[]{x,y+1});
        }
        return res;
    }
}

• 时间复杂度：最坏情况下，机器人需要遍历左右单元格，复杂度是O(m*n)
• 空间复杂度：最坏情况下，需要存储所有单元格的索引，所以空间复杂度为O(m*n)