题目:地上有一个m行n列的方格。一个机器人从坐标(0, 0)的格子开始移动,它每一次可以向左、右、上、下移动一格,但不能进入行坐标和列坐标的数位之和大于k的格子。例如,当k为18时,机器人能够进入方格(35, 37),因为3+5+3+7=18。但它不能进入方格(35, 38),因为3+5+3+8=19。请问该机器人能够到达多少个格子?
完整代码:
class Solution {
public:
int movingCount(int threshold, int rows, int cols)
{
//检查输入的合法性
if(threshold<0||rows<=0||cols<=0)
return 0;
// 创建一个访问情况的矩阵
bool* Visited = new bool[rows*cols];
//将矩阵初始化为false
memset(Visited, 0,rows*cols);
//计算可以到达的格子数,从(0,0)位置开始
int count=movingCountCore(threshold, rows, cols, 0, 0,Visited);
//删除辅助空间
delete[] Visited;
//返回最终可达到的格子数
return count;
}
private:
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+1, col, Visited)
+ movingCountCore(threshold, rows, cols, row, col-1, 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)
{
//判断当前点是否在合适的范围、行列坐标的数位之和不大于k的格子且没有被范访问过
if(row>=0&&row<rows&&col>=0&&col<cols&&getDigitSum(row)+getDigitSum(col)<=threshold&&!Visited[row*cols+col])
return true;
else
return false;
}
//求行位数和列位数之和
int getDigitSum(int number)
{
int sum = 0;
while (number>0)
{
//求最低位的数字之和
sum +=number%10;
//去除最低位
number /=10;
}
//返回行位数和列位数之和
return sum;
}
};