题目描述
C++ DFS和BFS两种实现的代码
算法一DFS
C++ 代码
class Solution {
public:
int table[51][51] = {};
int _rows;
int _cols;
int k;
int res = 1;
int dis[4][2]=
{
{ 0, -1 }, //左
{ 1, 0 }, //下
{ 0, 1 }, //右
{ -1, 0 }, //上
};
int movingCount(int threshold, int rows, int cols)
{
k = threshold;
_rows = rows;
_cols = cols;
if(rows <= 0 && cols <= 0) return 0;
table[0][0] = 1;
dfs(0, 0);
return res ;
}
private:
void dfs(int rows, int cols){
for(int i = 0; i < 4; i++){
int x = rows + dis[i][0];
int y = cols + dis[i][1];
if((sum(x) + sum(y) <= k) && (x >= 0 && x < _rows && y >= 0 && y < _cols) && (table[x][y] == 0)){
table[x][y] = 1;
res ++;
dfs(x, y);
}
}
}
int sum(int a){
int re = 0;
while(a){
re += a % 10;
a /= 10;
}
return re;
}
};
算法二BFS
C++ 代码
class Solution {
public:
int movingCount(int threshold, int rows, int cols)
{
vector<vector<bool>> table(rows, vector<bool>(cols, false));
queue<pair<int, int>> q;
int res = 0;
int dis[4][2] = {
{0, -1},//left
{1, 0},//down
{0, 1},//right
{-1, 0} //up
};
pair<int, int> p(0, 0);
q.push(p);
if(rows <= 0 && cols <= 0) return 0;
while(q.size()){
pair<int, int> a = q.front();
q.pop();
int x = a.first;
int y = a.second;
if(get_sum(x) + get_sum(y) <= threshold && (table[x][y] == false)){
res ++ ;
table[x][y] = true;
for(int i =0 ;i < 4; i++){
int _x = x + dis[i][0];
int _y = y + dis[i][1];
if(_x >= 0 && _x < rows && _y >= 0 && _y < cols ){
q.push({_x,_y});
}
}
}
}
return res;
}
private:
int get_sum(int a){
int res = 0;
while(a){
res += a % 10;
a /= 10;
}
return res;
}
};