题目描述

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

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

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

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

样例

输入：k=7, m=4, n=5

输出：20

BFS

typedef pair<int,int> PII;

const int N = 55;
bool vst[N][N];


class Solution {
public:

    int getBitSum(int x){
        int r = 0;
        while(x){
            r += x%10;
            x /= 10;
        }
        return r;
    }
    int movingCount(int k, int rows, int cols)
    {
        if(rows==0 && cols == 0) return 0;  //很奇怪,必须加这句话

        queue<PII> q;
        q.push({0,0});
        vst[0][0] = true;

        int count = 1;

        int dx[] = {0,1,0,-1}, dy[] = {1,0,-1,0};

        while(!q.empty()){
            PII v = q.front();
            q.pop();
            int x = v.first, y = v.second;
            for(int i = 0; i < 4; i++){
                int a = x + dx[i], b = y + dy[i];
                if(a >= 0 && a < rows && b >= 0 && b < cols 
                && !vst[a][b] && getBitSum(a)+getBitSum(b) <= k){
                    vst[a][b] = true;
                    q.push({a,b});
                    count ++;
                }
            }
        }

        return count;
    }
};