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

Beijing_duck_ · 2025-10-24 23:15:31 · 题解

[JOI2023 预选赛 R2] 填充 / Painting

by Beijing_duck_ 2025/10/24
蒟蒻的首篇题解，管理大大见谅见谅

题意简述

• JOI 君在一个 H \times W 的网格中进行一次填充，求此次填充后的联通区域面积值最大
• 这里填充后可能与外围的块合并

思路

• 一道简单的模拟题
• 首先你需要找出最初的连通块，这里你 bfs 或者 dfs 都行，在这个过程中记录三样东西：每个单元格所属的区域，每个区域的大小和颜色
• 然后构建区域之间的邻接表
• 遍历所有区域，考虑改变颜色为相邻的颜色之一（这里必须先扫一遍初始的区域大小，不然直接爆零）然后取最大值输出

::::success[AC代码]

#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;
}

::::