题目

地上有一个 m 行和 n 列的方格，横纵坐标范围分别是 0∼m−1 和 0∼n−1。

一个机器人从坐标 (0,0) 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格。

但是不能进入行坐标和列坐标的数位之和大于 k 的格子。

请问该机器人能够达到多少个格子？

示例

• 示例1

• 输入：k=7, m=4, n=5
• 输出：20

• 示例2

• 输入：k=18, m=40, n=40
• 输出：1484

解释：当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。

代码

解法：BFS

class Solution {
public:
    int getSum(int x,int y){ 
        return x / 10 + x % 10 + y / 10 + y % 10;
    }
    int movingCount(int m, int n, int k) {
        int res = 0;
        if(getSum(0,0) > k || !m || !n) return res;
        vector<vector<bool>> st(m,vector<bool>(n,false));   // 标志已访问
        int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1}; // 开方向数组
        queue<pair<int,int>> q;     // 存坐标
        q.push({0,0});
        st[0][0] = true;
        while(q.size()){
            auto t = q.front();
            q.pop();
            res++;
            int a,b;
            for(int i = 0; i < 4; i++){
                a = t.first + dx[i];
                b = t.second + dy[i];
                if(a >= 0 && a < m && b >= 0 && b < n && !st[a][b] && getSum(a,b) <= k){
                    q.push({a,b});
                    st[a][b] = true;
                }
            }
        }
        return res;
    }
};

代码分析：这道题也是第二次见了，以后可以照着这个思路写，没问题。详见文章

题目：机器人的运动范围