专栏文章
题解:P14299 [JOI2023 预选赛 R2] 填充 / Painting
P14299题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @minidf3c
- 此快照首次捕获于
- 2025/12/02 02:54 3 个月前
- 此快照最后确认于
- 2025/12/02 02:54 3 个月前
[JOI2023 预选赛 R2] 填充 / Painting
by
蒟蒻的首篇题解,管理大大见谅见谅
Beijing_duck_ 2025/10/24蒟蒻的首篇题解,管理大大见谅见谅
题意简述
- JOI 君在一个 的网格中进行一次填充,求此次填充后的联通区域面积值最大
- 这里填充后可能与外围的块合并
思路
- 一道简单的模拟题
- 首先你需要找出最初的连通块,这里你
bfs或者dfs都行,在这个过程中记录三样东西:每个单元格所属的区域,每个区域的大小和颜色 - 然后构建区域之间的邻接表
- 遍历所有区域,考虑改变颜色为相邻的颜色之一(这里必须先扫一遍初始的区域大小,不然直接爆零)然后取最大值输出
AC代码
CPP#include "bits/stdc++.h"
using namespace std;
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int H, W;
cin >> H >> W;
vector<vector<int>> A(H, vector<int>(W));
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
cin >> A[i][j];
}
}
// 查连通区域
vector<vector<int>> comp(H, vector<int>(W, -1));
vector<int> comp_size;
vector<int> comp_color;
int comp_count = 0;
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
if (comp[i][j] != -1) continue;
int color = A[i][j];
queue<pair<int, int>> q;
q.push({i, j});
comp[i][j] = comp_count;
int size = 0;
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
size++;
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx >= 0 && nx < H && ny >= 0 && ny < W &&
comp[nx][ny] == -1 && A[nx][ny] == color) {
comp[nx][ny] = comp_count;
q.push({nx, ny});
}
}
}
comp_size.push_back(size);
comp_color.push_back(color);
comp_count++;
}
}
// 构建区域的邻接表
vector<unordered_set<int>> adj(comp_count);
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
for (int d = 0; d < 4; d++) {
int ni = i + dx[d];
int nj = j + dy[d];
if (ni >= 0 && ni < H && nj >= 0 && nj < W) {
int c1 = comp[i][j];
int c2 = comp[ni][nj];
if (c1 != c2) {
adj[c1].insert(c2);
adj[c2].insert(c1);
}
}
}
}
}
int max_score = 0;
for (int i = 0; i < comp_count; i++) {
max_score = max(max_score, comp_size[i]);
}
for (int i = 0; i < comp_count; i++) {
// 考虑改为相邻区域的颜色
unordered_map<int, int> color_groups;
for (int neighbor : adj[i]) {
int neighbor_color = comp_color[neighbor];
color_groups[neighbor_color] += comp_size[neighbor];
}
for (auto& [color, total_size] : color_groups) {
// 如果改为这个颜色,总大小 = 当前区域大小 + 所有相邻的同色区域大小
max_score = max(max_score, comp_size[i] + total_size);
}
}
cout << max_score << endl;
return 0;
}
相关推荐
评论
共 0 条评论,欢迎与作者交流。
正在加载评论...