机器人的运动范围

问题陈述

地上有一个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。请问该机器人能够到达多少个格子？

DFS深度优先遍历

深度优先搜索： 可以理解为暴力法模拟机器人在矩阵中的所有路径。DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。
剪枝： 在搜索中，遇到数位和超出目标值、此元素已访问，则应立即返回，称之为 可行性剪枝 。

算法解析：

递归参数： 当前元素在矩阵中的行列索引 i 和 j ，两者的数位和 si, sj 。
终止条件： 当 ① 行列索引越界 或 ② 数位和超出目标值 k 或 ③ 当前元素已访问过 时，返回 0 ，代表不计入可达解。

递推工作：
标记当前单元格 ：将索引 (i, j) 存入 Set visited 中，代表此单元格已被访问过。
搜索下一单元格： 计算当前元素的 下、右 两个方向元素的数位和，并开启下层递归 。
回溯返回值： 返回 1 + 右方搜索的可达解总数 + 下方搜索的可达解总数，代表从本单元格递归搜索的可达解总数（起始点左上角【0，0】位置）。

附：数位增量计算：

由于机器人每次只能移动一格（即只能从 x运动至 x±1），因此每次只需计算 x到x±1 的数位和增量。本题说明1≤n,m≤100 ，以下公式仅在此范围适用。

设x的数位为s_x, x+1的数位为s_(x+1)。

当(x+1)%10==0时，s_(x+1)=s_x-8,例如 19, 20 的数位和分别为 10, 2；

当(x+1)%10!=0时，s_(x+1)=s_x+1,例如 1, 2的数位和分别为 1, 2。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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||si+sj>k||visisted[i][j]) return 0;
        visited[i][j]=true;
        return 1+dfs(i+1,j,(i+1)%10==0? si-8:si+1,sj)+dfs(i,j+1,si,(j+1)%10==0? sj-8:sj+1);
    }
}

BFS广度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution{
    public int movingCount(int m,int n,int k){
        boolean[][] visited=new boolean[m][n];
        int res=0;
        Queue<int[]> queue=new LinkedList<int[]>();//学习以下两行代码写法
        queue.add(new int[] {0,0,0,0});
        while(queue.size()>0){
            int[] index=queue.poll();
            int i=index[0],j=index[1],si=index[2],sj=index[3];
            if(i>=m||j>=n||si+sj>k||visited[i][j]) continue;
            visited[i][j]=true;
            res++;
            queue.add(new int[] {i+1,j,(i+1)%10==0? si-8:si+1,sj});
            queue.add(new int[] {i,j+1,si,(j+1)%10==0? sj-8:sj+1})
        }
        return res;
    }
}