BFS
class Solution {
public:
int movingCount(int threshold, int rows, int cols){
typedef pair<int, int> pii;
bool vis[rows][cols];
memset(vis, false, sizeof vis);
if(threshold < 0 || rows == 0 || cols == 0) return 0;
int cnt = 0;
queue<pii> qu;
qu.push({0, 0});
vis[0][0] = true, cnt ++ ;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};
while(!qu.empty()){
pii now = qu.front();
qu.pop();
for(int i = 0; i < 4; i ++ ){
int xx = now.first + dx[i];
int yy = now.second + dy[i];
if(xx < 0 || xx >= rows || yy < 0 || yy >= cols) continue;
if(vis[xx][yy]) continue;
int sum = 0, tmp = xx;
while(tmp){
sum += tmp % 10;
tmp /= 10;
}
tmp = yy;
while(tmp){
sum += tmp % 10;
tmp /= 10;
}
if(sum > threshold) continue;
qu.push({xx, yy});
vis[xx][yy] = true, cnt ++ ;
}
}
return cnt;
}
};
DFS
class Solution {
public:
vector<vector<bool>> vis;
int rows, cols, threshold;
int cnt;
int dic[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
void dfs(int x, int y){
vis[x][y] = true;
cnt ++ ;
for(int i = 0; i < 4; i ++ ){
int xx = x + dic[i][0];
int yy = y + dic[i][1];
if(xx < 0 || yy < 0 || xx >= rows || yy >= cols) continue;
if(vis[xx][yy]) continue;
int sum = 0;
int tx = xx, ty = yy;
while(tx){
sum += tx % 10;
tx /= 10;
}
while(ty){
sum += ty % 10;
ty /= 10;
}
if(sum <= threshold) dfs(xx, yy);
}
}
int movingCount(int _threshold, int _rows, int _cols){
rows = _rows, cols = _cols, threshold = _threshold;
vis = vector(rows, vector<bool>(cols, false));
if(threshold < 0 || rows == 0 || cols == 0) return 0;
cnt = 0;
dfs(0, 0);
return cnt;
}
};