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

题目

地上有一个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 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！