题意解析 使用 BFS/DFS\tt{BFS/DFS}BFS/DFS 或者 并查集\tt{并查集}并查集 所有不同的连通块进行标记。 统计网格中连通块的数量记为 kkk，白色方格的数量为 www。 遍历所有 白色\tt{白色}白色 方格，统计每个白色方格周围不同的连通块数量，记为 cic_ici ，那么如果将当前方格染为 黑色\tt{黑色}黑色，网格上的连通块的数量变为为 k−ci+1k - c_i + 1k−ci +1。求出所有的 k−ci+1k - c_i + 1k−ci +1，最后的答案为 ∑i=1wk−ci+1w\frac{{\sum_{i=1}^{w}{k - c_i + 1}}}{w}w∑i=1w k−ci +1 。 AC代码 复杂度分析 使用 BFS/DFS\tt{BFS/DFS}BFS/DFS 标记网格中所有的连通块的时间复杂度为 O(N×M)\mathrm{O}(N \times M)O(N×M)。 枚举 白色\tt{白色}白色 方格的时间复杂度为 O(N×M)\mathrm{O}(N \times M)O(N×M)。

#include <iostream> #include <vector> #include <queue> #include <set> #include <iomanip> #include <string> using i64 = long long; constexpr int dirs[][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; int main() { stdiossync_with_stdio(false); std::cin.tie(nullptr); }