用队列维护被迫补牛的位置，每加入一头牛后只重新检查它和四邻域的舒适状态。
OJ: usaco
题目 ID: 1110
难度:普及/提高-
标签:模拟BFS网格usaco
日期: 2026-07-11 19:42
题意
在无限网格上依次加入
如果某头奶牛上下左右四个相邻格子中恰好有 3 个有奶牛，那么它是“舒适的”。为了消除舒适状态，必须在唯一空着的相邻格子补一头奶牛。
每加入一头原始奶牛后，输出为了让当前所有奶牛都不舒适，还需要额外补多少头奶牛。
思路
先看一个小数据写法。它用 set 存所有已有奶牛，逻辑和满分做法一样，但每次查找用平衡树，适合帮助理解。
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-07-11 19:42
* update_at: 2026-07-11 19:44
*/
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;
int n;
set<pair<int, int> > cow;
queue<pair<int, int> > q;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
bool exists_cow(int x, int y) {
return cow.find(make_pair(x, y)) != cow.end();
}
void check_comfortable(int x, int y) {
if (!exists_cow(x, y)) return;
int cnt = 0;
int empty_x = 0;
int empty_y = 0;
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (exists_cow(nx, ny)) {
cnt++;
} else {
empty_x = nx;
empty_y = ny;
}
}
if (cnt == 3) {
q.push(make_pair(empty_x, empty_y));
}
}
void process_queue() {
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
if (exists_cow(x, y)) continue;
cow.insert(make_pair(x, y));
check_comfortable(x, y);
for (int d = 0; d < 4; d++) {
check_comfortable(x + dx[d], y + dy[d]);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
int x, y;
cin >> x >> y;
q.push(make_pair(x, y));
process_queue();
cout << (int)cow.size() - i << '\n';
}
return 0;
}核心观察很直接：如果一头奶牛已经有 3 个相邻奶牛，那么第 4 个位置必须补上，否则这头牛永远舒适。
这种补牛可能继续触发连锁反应，所以可以用队列维护“需要尝试补牛的位置”。
舒适状态只和一个格子以及它的四个相邻格子有关。加入一头牛后，只有下面这些位置可能状态改变：
| 位置 | 为什么要重新检查 |
|---|---|
| 新加入的格子 | 它自己可能已经有 3 个邻居 |
| 上下左右四邻格子 | 它们的相邻牛数量刚刚变化 |
每次从队列取出一个位置：
- 如果这个位置已经有牛，跳过；
- 否则在这里补一头牛；
- 检查这头新牛和它四周的牛是否变舒适；
- 若某头牛舒适，就把它缺的那个格子放入队列。
样例中第 4 次加入后形成：
text
.C.
CCC
...中间那头牛有 3 个相邻奶牛，所以必须在第 4 个方向补上一头牛。
注意一个细节：如果某个给定的原始奶牛位置之前已经被自动补过，那么这次“加入原始奶牛”不会让总牛数增加，但额外牛数量要减少 1。代码统一维护当前实际牛总数 total_cows，第 i 次输出 total_cows - i。
代码
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-07-11 19:42
* update_at: 2026-07-11 19:44
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXG = 3005;
const int SHIFT = 1000;
int n;
bool has_cow[MAXG][MAXG];
queue<pair<int, int> > q;
int total_cows;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
void check_comfortable(int x, int y) {
if (!has_cow[x][y]) return;
int cnt = 0;
int empty_x = -1;
int empty_y = -1;
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (has_cow[nx][ny]) {
cnt++;
} else {
empty_x = nx;
empty_y = ny;
}
}
if (cnt == 3) {
q.push(make_pair(empty_x, empty_y));
}
}
void process_queue() {
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
if (has_cow[x][y]) continue;
has_cow[x][y] = true;
total_cows++;
check_comfortable(x, y);
for (int d = 0; d < 4; d++) {
check_comfortable(x + dx[d], y + dy[d]);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
int x, y;
cin >> x >> y;
x += SHIFT;
y += SHIFT;
q.push(make_pair(x, y));
process_queue();
cout << total_cows - i << '\n';
}
return 0;
}复杂度
每个格子最多真正加入一次；每次加入只检查常数个附近位置。
时间复杂度为
空间复杂度为网格数组大小。
总结
本题的关键是局部维护：舒适与否只受四邻域影响。
用队列保存“被迫补牛”的位置，就能把所有连锁反应自然处理完；答案用当前总牛数减去已经处理的原始牛数量得到。