题目描述
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
思路
与《矩阵中的路径》类似，但这道题不需要回溯，因为如果满足条件一定可以走到。而《矩阵中的路径》如果路径走不通，需要回溯。
思路1：通过递归的去查找某一个下标位置的两个方向即可（要么往右要么往下），在到达某一个位置的时候，判断是否越界，是否被访问过，是否满足数位之和小于k （最优解）
思路2：逐个遍历每一个方格，判断数位之和是否小于等于k，并且判断当前位置能否由 上边的位置 和 左边的位置 走来即可。 （如果k=0时，仍需要不断判断，该方法效率较低）
☆☆解法1
public class Solution { private int sum = 0; public int movingCount(int threshold, int rows, int cols) { boolean[][] vis = new boolean[rows][cols]; solve(0,0,rows,cols,threshold,vis); return sum; } // 牢记如何求位数和！！ private int cal(int num){ int res = 0; while (num > 0){ res += num % 10; num /= 10; } return res; } private void solve(int x, int y, int rows, int cols, int k, boolean[][] vis) { if (x < 0 || y < 0 || x >= rows || y >= cols || vis[x][y] || (cal(x) + cal(y) > k)){ return; } // 当前位置(x,y)是可以走的，那么就从当前位置往右下移动即可。 vis[x][y] = true; sum++; solve(x,y+1,rows,cols,k,vis); // 右 solve(x+1,y,rows,cols,k,vis); // 下 // 既然不用回溯，就不需要递归x-1和y-1的坐标了，因为从左上角出发，每次只需要往右和往下搜索 // solve(x-1,y,rows,cols,k,vis); // solve(x,y-1,rows,cols,k,vis); } }
☆解法2
public class Solution { public int movingCount(int threshold, int rows, int cols) { int sum = threshold >= 0 ? 1 : 0; boolean[][] vis = new boolean[rows][cols]; vis[0][0] = true; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if ((cal(i) + cal(j)) <= threshold){ // 判断能否从上边走过来 if (i-1 >= 0 && vis[i-1][j]){ sum++; vis[i][j] = true; // 判断能否从左边走过来 }else if (j-1 >= 0 && vis[i][j-1]){ sum++; vis[i][j] = true; } } } } return sum; } private int cal(int num){ int res = 0; while (num > 0){ res += num % 10; num /= 10; } return res; } }