船泊湘风晚
花谢烟雨迟
C++，dfs，遍历所有符合条件的点。
说实话，这种题目，我第一感觉就是这是道数学题，然后苦思冥想，没有找到规律，遂想先暴力试试，结果3ms,。。。
如果确实是这样的话，这题就没有难度了。
遍历所有满足条件的点，计数即可。
满足以下三个条件：
- 在矩形范围内
- 行坐标和列坐标的数位之和<=k
- 没有遍历过
还有注意的就是一维和二维的转换，这个应该说了就懂。
下面是代码：
class Solution {
public:
int movingCount(int threshold, int rows, int cols) {
vector<bool> vis(rows * cols, false);
if (threshold <= 0) return 0;
return dfs(vis, 0, rows, cols, threshold);
}
int dfs(vector<bool> &vis, int curr, int &r, int &c, int &k) {
vis[curr] = true;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int sum = 1;
for (int i = 0; i < 4; i++) {
int tx = curr / c + dx[i], ty = curr % c + dy[i];
int next = tx * c + ty;
if (0 <= tx && tx < r && 0 <= ty && ty < c && !vis[next] && get_sum(tx) + get_sum(ty) <= k)
sum += dfs(vis, next, r, c, k);
}
return sum;
}
int get_sum(int num) {
int ans = 0;
while (num) {
ans += num % 10;
num /= 10;
}
return ans;
}
};
