13 机器人的运动范围
地上有一个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
class Solution {
int count;
public int movingCount(int m, int n, int k) {
boolean[][] visited = new boolean[m][n];
count=0;
dfs(0,0,visited,k,m,n);
return count;
}
private void dfs(int i, int j, boolean[][] visited, int k, int m, int n){
count++;
visited[i][j]=true;
if(i-1>=0 && !visited[i-1][j] && access(i-1,j,k)) dfs(i-1, j, visited, k, m, n);
if(i+1<m && !visited[i+1][j] && access(i+1,j,k)) dfs(i+1, j, visited, k, m, n);
if(j-1>=0 && !visited[i][j-1] && access(i,j-1,k)) dfs(i, j-1, visited, k, m, n);
if(j+1<n && !visited[i][j+1] && access(i,j+1,k)) dfs(i, j+1, visited, k, m, n);
}
private boolean access(int i, int j, int k){
int sum=0;
while(i>0){
sum+=i%10;
i/=10;
}
while(j>0){
sum+=j%10;
j/=10;
}
return sum<=k;
}
}
描述：
地上有一个 rows 行和 cols 列的方格。坐标从 [0,0] 到 [rows-1,cols-1] 。一个机器人从坐标 [0,0] 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于 threshold 的格子。 例如，当 threshold 为 18 时，机器人能够进入方格 [35,37] ，因为 3+5+3+7 = 18。但是，它不能进入方格 [35,38] ，因为 3+5+3+8 = 19 。请问该机器人能够达到多少个格子？
深度优先搜索
public class Solution {
public int movingCount(int threshold, int rows, int cols) {
boolean[][] visited = new boolean[rows][cols];
if(threshold<0 || rows<=0 || cols <=0) return 0;
return movingCountCore(threshold, rows, cols, 0, 0, visited);
}
private int movingCountCore(int threshold, int rows, int cols, int row, int col, boolean[][] visited){
int count=0;
if(check(threshold, rows, cols, row, col, visited)){
return 1 + movingCountCore(threshold, rows, cols, row+1, col, visited)
+ movingCountCore(threshold, rows, cols, row-1, col, visited)
+ movingCountCore(threshold, rows, cols, row, col+1, visited)
+ movingCountCore(threshold, rows, cols, row, col-1, visited);
}
return count;
}
private boolean check(int threshold, int rows, int cols, int row, int col, boolean[][] visited){
if(row<0 || col<0 || row==rows || col==cols) return false;
if(visited[row][col]) return false;
if(getDigitSum(row) +getDigitSum(col) <= threshold){
visited[row][col]=true;
return true;
}
return false;
}
private int getDigitSum(int i){
int res=0;
while(i>0){
res+=i%10;
i/=10;
}
return res;
}
}