专栏文章

题解: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 君在一个 H×WH \times W 的网格中进行一次填充,求此次填充后的联通区域面积值最大
  • 这里填充后可能与外围的块合并

思路

  • 一道简单的模拟题
  • 首先你需要找出最初的连通块,这里你 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 条评论,欢迎与作者交流。

正在加载评论...