BFS
class Solution {
public:
int cal_single(int x)
{
int res = 0;
// 注意此处的判断条件!
for(; x != 0;)
{
int zuo = x/10;
int ge = x%10;
res = res + ge;
x = zuo;
}
return res;
}
bool is_xydy(int x, int y, int threshold)
{
return (cal_single(x) + cal_single(y)) <= threshold;
}
int bfs(int threshold, int rows, int cols)
{
int res = 0;
const int N = 60;
bool used[N][N] = {false};
queue<pair<int, int>> q;
q.push({0, 0});
used[0][0] = true;
++ res;
// 上 下 左 右
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
while(! q.empty())
{
pair<int, int> tmp = q.front();
q.pop();
for(int i = 0; i < 4; ++ i)
{
int x_t = tmp.first + dx[i];
int y_t = tmp.second + dy[i];
if(x_t >= 0 && x_t < rows && y_t >= 0 && y_t < cols && is_xydy(x_t, y_t, threshold) && used[x_t][y_t] == false)
{
q.push({x_t, y_t});
++ res;
used[x_t][y_t] = true;
}
}
}
return res;
}
int movingCount(int threshold, int rows, int cols)
{
if(threshold < 0 || rows <= 0 || cols <= 0)
{
return 0;
}
else
{
return bfs(threshold, rows, cols);
}
}
};
DFS
class Solution {
public:
static const int N = 60;
// bool used[N][N] = {false};
// 上 下 左 右
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int cal_sum(int x)
{
int res = 0;
while(x != 0)
{
int zuo = x/10;
int ge = x%10;
res = res + ge;
x = zuo;
}
return res;
}
bool is_true(int x, int y, int threshold)
{
int res = cal_sum(x) + cal_sum(y);
if(res <= threshold)
{
return true;
}
else
{
return false;
}
}
void dfs(int & res, int x, int y, bool used[][N], int threshold, int rows, int cols)
{
if(x < 0 || x >= rows || y < 0 || y >= cols)
{
return ;
}
else
{
if(used[x][y] == false && is_true(x, y, threshold))
{
++ res;
used[x][y] = true;
for(int i = 0; i < 4; ++ i)
{
int x_t = x + dx[i];
int y_t = y + dy[i];
dfs(res, x_t, y_t, used, threshold, rows, cols);
}
// 注意:根据题意,不能写此语句,
// 此处不重置,
// 并非恢复现场
// used[x][y] = false;
return ;
}
else
{
return ;
}
}
}
int movingCount(int threshold, int rows, int cols)
{
if(threshold < 0 || rows <= 0 || cols <= 0)
{
return 0;
}
else
{
int res = 0;
bool used[N][N] = {false};
dfs(res, 0, 0, used, threshold, rows, cols);
return res;
}
}
};