本文共 913 字，大约阅读时间需要 3 分钟。

题目

地上有一个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。请问该机器人能够到达多少个格子？

思路

昨天才做一个上下左右能走的题目，那么马上想到的就是DFS和BFS，但是仔细一想其实用遍历数组就能解决。

• 检查上面和左面有没有走过，检查数位和是否小于等于k，然后计数
• 结束的条件是某一行（比如第i行）的所有格子，机器人都不能抵达。

代码

class Solution {public:
int numsum(int i){
int s = 0;
while(i != 0){
s += i % 10;
i = i / 10;
}
return s;
}
int movingCount(int m, int n, int k) {
bool flag[m][n];
int sum = 0;
int sum_i=0;
int sum_j=0;
int res_old = 0;
for(int i = 0;i < m;i++){
if(i%10 == 0){
sum_i = i/10;
}else{
sum_i++;
}
for(int j = 0;j < n;j++){
if(j%10 == 0){
sum_j = j/10;
}else{
sum_j++;
}
if((j==0 || j>0 && flag[i][j-1]==true || i>0 && flag[i-1][j]==true) && sum_i+sum_j <= k){
sum++;
flag[i][j] = true;
}else{
flag[i][j] = false;
}
}
if(sum != res_old){
res_old = sum;
}else{
break;
}
}
return sum;
   }};

转载地址：https://blog.csdn.net/hanmin822/article/details/105572289 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！