DFS和BFS写法
DFS
class Solution{
public:
int movingCount(int m, int n, int k){
if(!m || !n)return 0;
vector<vector<bool>> visited(m, vector<bool>(n, false));
return dfs(0, 0, m, n, k,visited);
}
int get_double_sum(int x, int y){
int sum = 0;
while(x){
sum += x % 10;
x /= 10;
}
while(y){
sum += y % 10;
y /= 10;
}
return sum;
}
int dfs(int x, int y, int m, int n, int k, vector<vector<bool>>& visited){
if(x < 0 || x >= m || y < 0 || y >= n ||get_double_sum(x, y) > k
|| visited[x][y])return 0;
visited[x][y] = true;
return dfs(x, y + 1, m, n, k, visited) +
dfs(x + 1, y, m, n, k, visited) + 1;
}
};
BFS
class Solution {
public:
int get_double_sum(pair<int, int> t){
int sum = 0;
while(t.first){
sum += t.first % 10;
t.first /= 10;
}
while(t.second){
sum += t.second % 10;
t.second /= 10;
}
return sum;
}
int movingCount(int m, int n, int k) {
if(!m || !n)return 0;
queue<pair<int, int>> q;
int res = 0;
vector<vector<bool>> flag(m, vector<bool>(n, false));
q.push({0, 0});
int dx[] = {0, 1}, dy[] = {1, 0};
while(!empty(q)){
pair<int, int> t = q.front();
q.pop();
if(get_double_sum(t) > k || flag[t.first][t.second])continue;//若该网格已经访问过 continue;
res ++ ;//若未访问
flag[t.first][t.second] = true;//记录
for(int i = 0; i < 2; i ++ ){
int a = t.first + dx[i], b = t.second + dy[i];
if(a >= 0 && a < m && b >= 0 && b < n){
q.push({a, b});
}
}
}
return res;
}
};