Comfortable Cows问题：代码实现、解释与复杂度分析

```cpp #include <iostream> #include <vector> #include <set> using namespace std; // 检查一个点是否有奶牛 bool hasCow(int x, int y, set<pair<int, int>>& cows) { return cows.find({x, y}) != cows.end(); } // 检查一头奶牛是否舒适 bool isComfortable(int x, int y, set<pair<int, int>>& cows) { int count = 0; if (hasCow(x - 1, y, cows)) count++; if (hasCow(x + 1, y, cows)) count++; if (hasCow(x, y - 1, cows)) count++; if (hasCow(x, y + 1, cows)) count++; return count == 3; } // 检查一个点周围是否有舒适的奶牛 bool hasComfortableAround(int x, int y, set<pair<int, int>>& cows) { if (hasCow(x, y, cows) && isComfortable(x, y, cows)) return true; if (hasCow(x - 1, y, cows) && isComfortable(x - 1, y, cows)) return true; if (hasCow(x + 1, y, cows) && isComfortable(x + 1, y, cows)) return true; if (hasCow(x, y - 1, cows) && isComfortable(x, y - 1, cows)) return true; if (hasCow(x, y + 1, cows) && isComfortable(x, y + 1, cows)) return true; return false; } int main() { int N; cin >> N; set<pair<int, int>> cows; int total = 0; for (int i = 0; i < N; i++) { int x, y; cin >> x >> y; cows.insert({x, y}); // 如果新加入奶牛后周围出现舒适的奶牛 if (hasComfortableAround(x, y, cows)) { // 找到需要添加的位置 vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; for (auto& dir : directions) { int newX = x + dir.first; int newY = y + dir.second; if (!hasCow(newX, newY, cows) && hasComfortableAround(newX, newY, cows)) { total++; cows.insert({newX, newY}); } } } cout << total << endl; } return 0; } ``` 代码解释 1. 数据结构：使用 `set<pair<int, int>> cows` 存储奶牛的坐标，借助 `set` 的特性可以高效地判断某坐标是否有奶牛。 2. 辅助函数： - `hasCow` 函数用于检查给定坐标处是否有奶牛。 - `isComfortable` 函数用于判断一头奶牛是否舒适，即其水平或竖直方向上与恰好三头其他奶牛相邻。 - `hasComfortableAround` 函数用于检查某个点周围是否有舒适的奶牛。 3. 主逻辑： - 循环 `N` 次，每次读取一头新奶牛的坐标并插入 `cows` 集合。 - 检查新加入奶牛后其周围是否有舒适的奶牛，若有则找到需要添加奶牛的位置，将其加入 `cows` 集合并更新 `total`。 - 输出当前需要添加的奶牛总数。 复杂度分析 - 时间复杂度：每次插入新奶牛后检查和添加新奶牛的操作时间复杂度为 $O(1)$，总共插入 $N$ 头奶牛，因此总的时间复杂度为 $O(N)$。 - 空间复杂度：使用了 `set` 存储奶牛坐标，最多存储 $N$ 头奶牛，因此空间复杂度为 $O(N)$。 ######[AI问答 | 956点数解答 | 2026-02-02 17:26:13]