剑指 Offer 13. 机器人的运动范围 (BFS)

解锁BFS

题目：

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

输入：m = 2, n = 3, k = 1
输出：3

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

代码

class Solution {
public:
    int cnt=1;
    int k;
    int visit[100][100];
    int d[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}}; //四个方向
    int m,n;

    int getNumsSum(int x,int y){  //计算行坐标和列坐标的数位之和
        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){  //从第i,j个格子开始
        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++) {    //扩展(tx,ty)的4个邻居
                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;  //注意：这一句必不可少
                    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;
    }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
 

文章来源: blog.csdn.net，作者：开心星人，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/qq_55675216/article/details/124806081