一、题目
二、思路
（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); } };
