Sword finger offer 13 Robot range of motion (BFS)

Unlock BFS

subject ：

There is one on the ground m That's ok n Grid of columns , From coordinates [0,0] To coordinates [m-1,n-1] . A robot from coordinates [0, 0] The grid starts to move , It can go left every time 、 Right 、 On 、 Move down one space （ Can't move out of the box ）, The sum of the digits of row coordinates and column coordinates is greater than k Lattice of . for example , When k by 18 when , Robots can enter the grid [35, 37] , because 3+5+3+7=18. But it can't get into the grid [35, 38], because 3+5+3+8=19. How many squares can the robot reach ？

Input ：m = 2, n = 3, k = 1
Output ：3

1 <= n,m <= 100
0 <= k <= 20

Code

class Solution {public:    int cnt=1;    int k;    int visit[100][100];    int d[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}}; // Four directions     int m,n;    int getNumsSum(int x,int y){  // Calculate the sum of digits of row coordinates and column coordinates         int sum=0;        while(x){            sum+=(x%10);            x/=10;        }        while(y){            sum+=(y%10);            y/=10;        }        return sum;    }    void bfs(int i,int j){  // From i,j Start with a grid         queue<pair<int,int> > q;        q.push({i,j});        visit[i][j]=1;        while(q.size()){            pair<int,int> t=q.front();            q.pop();            int tx=t.first,ty=t.second;            for (int i = 0; i < 4; i++) {    // Expand (tx,ty) Of 4 A neighbor                 int nx = tx + d[i][0], ny = ty + d[i][1];                if(nx< m && nx>=0 && ny>=0 && ny<n && visit[nx][ny]==0 && getNumsSum(nx,ny)<=k)             {                      visit[nx][ny] = 1;  // Be careful ： This sentence is indispensable                     cnt++;                    q.push({nx, ny});                }            }        }    }    int movingCount(int m, int n, int k) {        this->k=k;        this->m=m;        this->n=n;        bfs(0,0);        return cnt;    }};