题目描述
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如,当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18。但是,它不能进入方格(35,38),因为3+5+3+8 = 19。请问该机器人能够达到多少个格子?
public int count = 0;//用来保存访问格子数
public int movingCount(int threshold, int rows, int cols)
{
boolean[][] vis = new boolean[rows][cols];
solve(threshold,rows,cols,0,0,vis);
return count;
}
private void solve(int threshold, int rows,int cols,int x, int y,boolean[][] vis) {
if(x<0||x>=rows||y<0||y>=cols||vis[x][y]||isThreshold(threshold,x,y)) {
return;
}
vis[x][y] = true;
count++;//如果格子坐标数位和不符合要求那么不会执行到这一行代码在上面就return了
solve(threshold, rows,cols,x+1, y,vis);
solve(threshold, rows,cols,x-1,y,vis);
solve(threshold, rows,cols,x, y+1,vis);
solve(threshold, rows,cols,x, y-1,vis);
}
public boolean isThreshold(int threshold,int x,int y) {
int temp=0;
while(x%10!=0) {
temp+=x%10;
x=x/10;
}
while(y%10!=0) {
temp+=y%10;
y=y/10;
}
if(temp>threshold) {
return true;
}
return false;
}