此题作为平生第一道BFS
仅以纪念。
注意不要掉坑:从$(0,0)$
算法(BFS)
据说此题还有DFS的写法(肯定)
class Solution {
public:
int get_sum(int x, int y) {
int s = 0;
while (x) {
s += x % 10;
x /= 10;
}
while (y) {
s += y % 10;
y /= 10;
}
return s;
}
int movingCount(int threshold, int rows, int cols)
{
if (rows <= 0 & cols <= 0)
return 0;
bool b[rows + 5][cols + 5];
int ax[rows * cols + 5], ay[rows * cols + 5], front = 0, rear = 1;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
ax[0] = ay[0] = 0;
memset(b, true, sizeof(b));
b[0][0] = false;
while (front < rear) {
for (int k = 0; k < 4; k++) {
ax[rear] = ax[front] + dx[k], ay[rear] = ay[front] + dy[k];
if (ax[rear] >= 0 & ax[rear] < rows & ay[rear] >= 0 & ay[rear] < cols & b[ax[rear]][ay[rear]] & get_sum(ax[rear], ay[rear]) <= threshold)
b[ax[rear]][ay[rear]] = false, rear++;
}
front++;
}
return front;
}
};