题目描述
因为不需要回溯,所以直接dfs
C++ 代码
class Solution {
public:
int res = 0, m, n, limit;
bool st[50][50];
int movingCount(int threshold, int rows, int cols) {
m = rows, n = cols, limit = threshold;
if(m == 0 || n == 0) return 0;
dfs(0, 0);
return res;
}
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
void dfs(int x, int y) {
st[x][y] = true;
res++;
for(int i = 0;i < 4;i ++) {
int xa = x + dx[i], ya = y + dy[i];
int sum = xa / 10 + xa % 10 + ya / 10 + ya % 10;
if(!st[xa][ya] && sum <= limit && xa >= 0 && xa < n && ya >= 0 && ya < m) {
dfs(xa, ya);
}
}
}
};