题解：P14299 [JOI2023 预选赛 R2] 填充 / Painting

\(\displaystyle \large {题目传送门}\)

题面

给定一个一个 H*W 的矩形 ， 每个坐标上有一个颜色 ， 上下左右相邻的同颜色节点可以形成连通块 。
你可以对任意一个连通块 ， 进行一次并仅有一次的染色 ， 求新形成的连通块最大的大小 。

思路：

\(\mathcal Step\ 1:\)

我们既然要对连通块做操作 ， 那怎么有不求出所有连通块的理由呢 ？
问题是我们要对求出的连通块做些什么 ？
$\ $
扫图的过程中 ， 对于没有搜到过的点 ， 我们通过广搜确定这个连通块 。
先预处理出这个连通块所代表的编号 、 大小 、 代表点（这个很重要）。
搜的过程中 ， 我们统计当前连通块的大小 ， 并对搜到的所有合法的在当前连通块中的点进行染色 ， 以便我们第二遍的时候能够快速确定一些当前连通块的信息 。

\(\mathcal Step\ 2:\)

接下来 ， 我们发现这道题的数据很小 （是道绿色水题） ， 所以我们直接考虑对每个连通块枚举 。然后的操作是第二遍 BFS , 这次有所不同 。
$\ $
我们从代表点出发（这不就用到了？）， 寻找它的边界 ， 如果找到了一个接壤的连通块 ， 那就可以得到它的大小 和颜色， 并且给它打一个 “搜过了” 的标记 。
$\ $
对于得到的数据 ， 我们考虑对于每一种颜色丢一个桶 ， 统计某色连通块的大小和 ， 因为只要当前连通块改为某种颜色 ， 那么所有和它接壤的这种颜色的连通块都可以被它吸收 。
$\ $
如果每种颜色丢桶 ， 然后再一个一个遍历再查询最大值 ， 或许有损它绿题的称号（虽然也能过） ， 我们考虑在遍历过程中直接把这个得到的数据丢进优先队列 ， 搜完以后再直接取堆顶 。
$\ $
于是乎 ， 当前连通块加上堆顶就是这次查询的局部最优解 ， 我们和答案取个最大值就可以进行下一次枚举了 。
千万不要忘记判断优先队列为空的情况！

---

\(\displaystyle \mathcal {C_OD}\large {^E}\)

#include<bits/stdc++.h>
using namespace std;const int N = 505;//四向移动 
const int dx[] = {0, 1, -1, 0, 0};
const int dy[] = {0, 0, 0, 1, -1};int h, w;
int a[N][N];				//记录图的原始输入 
int vis[N][N];  			//bfs时的访问 
int cid[N][N];  			//连通块 的 编号 
int csz[N * N]; 			//连通块 的 大小 
int ccl[N * N]; 			//连通块 的 颜色 
int cnt;                    //连通块 的 数量 
pair<int, int> rep[N * N];  //连通块 的 代表点 
int ans = 0;void bfs(int sx, int sy) {queue<pair<int, int>> q; //队列记录坐标 q.push({sx, sy});vis[sx][sy] = 1;cnt++; //新建连通块编号 int col = a[sx][sy]; //记录颜色 int sz = 0; //初始化大小 rep[cnt] = {sx, sy}; //记录代表点 while (!q.empty()) {int x = q.front().first;int y = q.front().second;q.pop();cid[x][y] = cnt; //每个坐标都可以查询到它所处的连通块 sz++;for (int i = 1; i <= 4; i++) {int nx = x + dx[i];int ny = y + dy[i];//边界条件 if (nx < 1 || nx > h || ny < 1 || ny > w) continue;//连通性 if (vis[nx][ny] || a[nx][ny] != col) continue;vis[nx][ny] = 1;q.push({nx, ny});}}csz[cnt] = sz;ccl[cnt] = col;//存储数据 
}void BFS(int i){int sx = rep[i].first;int sy = rep[i].second;//用来统计特定颜色邻块的大小和 priority_queue<int> pq; //统计颜色大小 map<int, int> color_sum;//防止重复统计 unordered_set<int> counted;queue<pair<int, int>> q;q.push({sx, sy});//防止坐标重复访问 unordered_set<int> visited;//不要忘记初始化 visited.insert(sx * w + sy);while (!q.empty()) {int x = q.front().first;int y = q.front().second;q.pop();for (int k = 1; k <= 4; k++) {int nx = x + dx[k];int ny = y + dy[k];//边界条件 if (nx < 1 || nx > h || ny < 1 || ny > w) continue;int nid = cid[nx][ny];if (nid == i) {// 同一连通块，继续探索int key = nx * w + ny;if (visited.count(key)) continue;visited.insert(key);q.push({nx, ny});} else {// 不同连通块，统计大小if (!counted.count(nid)) {color_sum[ccl[nid]] += csz[nid]; //累计大小 pq.push(color_sum[ccl[nid]]); // 将颜色总和加入优先队列counted.insert(nid);}}}}if (!pq.empty()) { //取出堆顶，统计最终大小 ans = max(ans, csz[i] + pq.top());}else{ans = max(ans, csz[i]);}
} int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin >> h >> w;for (int i = 1; i <= h; i++) {for (int j = 1; j <= w; j++) {cin >> a[i][j];}}// 第一步：识别所有连通块for (int i = 1; i <= h; i++) {for (int j = 1; j <= w; j++) {if (!vis[i][j]) {bfs(i, j);}}}// 第二步：从代表点出发进行边界探索for (int i = 1; i <= cnt; i++) {BFS(i);}cout << ans << endl;return 0;
}