一、题目

二、思路

（1）求数位之和就while循环，每次循环求余；
（2）bfs或者dfs都可以，如果用bfs则用到队列，遍历时为了防止重复遍历和遇到不合法的格子，在push入队列之前进行判断。

三、代码

class Solution {
private:
    vector<pair<int, int>>directions{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    //获取数位之和
    int getNum(int x){
        int ans = 0;
        while(x){
            int temp = x % 10;
            x = x / 10;
            ans += temp;
        }
        return ans;
    }
public:
    int movingCount(int m, int n, int k) {
        //从(0, 0)出发
        queue<pair<int, int>>q;
        vector<vector<bool>> vis(m, vector<bool>(n,false));
        vis[0][0] = true;
        q.push(make_pair(0, 0));
        int ans = 1;
        while(!q.empty()){
            pair<int, int>a = q.front();
            int x = a.first, y = a.second;
            q.pop();
            for(auto dir: directions){
                int newx = x + dir.first, newy = y + dir.second;
                if(isarea(m, n, newx, newy) && getNum(newx) + getNum(newy) <= k 
                   && !vis[newx][newy]){
                    vis[newx][newy] = true;
                    q.push(make_pair(newx, newy));
                    ans++;
                }
            }
        }
        return ans;
    }
    bool isarea(int m, int n, int x, int y){
        return (x >= 0 && x < m && y >= 0 && y < n);
    }
};

  

 

  
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
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/122610089