面试题13:机器人的运动范围
程序员文章站
2022-06-25 16:22:56
题目:地上有一个m行n列的方格。一个机器人从坐标(0,0)的格子开始移动,它每次可以向左、右、上、下移动一格,但不能进入行坐标和列坐标的数位之和大于k的格子。例如,当k为18时,机器人能够进入方格(35,37),因为3+5+3+7=18。但它不能进入方格(35,38),因为3+5+3+8=19。请问该机器人能够到达多少个格子?int movingCount(int threshold,int rows,int cols){ if(threshold<0||rows<=0||cols&...
题目:地上有一个m行n列的方格。一个机器人从坐标(0,0)的格子开始移动,它每次可以向左、右、上、下移动一格,但不能进入行坐标和列坐标的数位之和大于k的格子。例如,当k为18时,机器人能够进入方格(35,37),因为3+5+3+7=18。但它不能进入方格(35,38),因为3+5+3+8=19。请问该机器人能够到达多少个格子?
int movingCount(int threshold,int rows,int cols)
{
if(threshold<0||rows<=0||cols<=0)
return 0;
bool *visited=new bool[rows*cols];
for(int i=0;i<rows*cols;i++)
visited[i]=false;
int count=movingCountCore(threshold,rows,cols,0,0,visited);
delete[] visited;
return count;
}
int movingCountCore(int threshold,int rows,int cols,int row,int col,bool* visited)
{
int count=0;
if(check(threshold,rows,cols,row,col,visited))
{
visited[row*cols+col]=true;
count=1+movingCountCore(threshold,rows,cols,row-1,col,visited)+
movingCountCore(threshold,rows,cols,row,col-1,visited)+
movingCountCore(threshold,rows,cols,row+1,col,visited)+
movingCountCore(threshold,rows,cols,row,col+1,visited);
}
return count;
}
bool check(int threshold,int rows,int cols,int row,int col,bool* visited)
{
if(row>=0&&row<rows&&col>=0&&col<cols&&getDigitSum(row)+getDigitSum(col)<=threshold&&!visited[row*cols+col])
return true;
return false;
}
int getDigitSum(int number)
{
int sum=0;
while(number>0)
{
sum+=number%10;
number/=10;
}
return sum;
}
本文地址:https://blog.csdn.net/weixin_42729072/article/details/107893992