P11724 [JOIG 2025] ポスター 2 / Poster 2

#include <iostream>
#include <algorithm>
#include <map>
#include <cstdio>
#define x first
#define y second
#define PII pair<int, int>
using namespace std;
typedef long long LL;

int n, k, g[300][300], maxn, max_x, max_y, minn, color, cnt, ans;
map<int, int> mp1, mp3;
map<PII, int> mp2;
int dx[] = {0, 0, 1, 1};
int dy[] = {0, 1, 0, 1};

bool in(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= n;
}

int main() {
#ifdef ExRoc
    freopen("test.txt", "r", stdin);
#endif // JiuQi

    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            scanf("%d", &g[i][j]);
        }
    }
    //判断要修改哪一个格子
    for (int i = 1; i <= n - 1; ++i) {
        for (int j = 1; j <= n - 1; ++j) {
            mp1.clear(); // 将mp1清空，方便下一次四个格子中颜色的记录
            for (int r = 0; r < 4; ++r) {
                mp1[g[i + dx[r]][j + dy[r]]]++;
            }
            if (mp1.size() >= 3) ans++;
            //每次将四个格子中出现颜色两次的格子标记出来，用mp2记录他出现的次数 ，但只标记同种颜色出现次数大于1的格子，因为如果只出现一次，那那种颜色改了和没改没区别
            if (mp1.size() == 2) {
                for (const auto& t : mp1) {
                    if (t.y > 1) {
                        for (int r = 0; r < 4; r++) {
                            if (mp1[g[i + dx[r]][j + dy[r]]] == t.y) {
                                mp2[{i + dx[r], j + dy[r]}]++;
                            }
                        }
                    }
                }
            }
        }
    }
    //将格子数出现次数最多的格子找出来，即为要改变的格子
    for (const auto& t : mp2) {
        if (t.y > maxn) {
            maxn = t.y;
            max_x = t.x.x;
            max_y = t.x.y;
        }
    }
    //要修改的格子周围加上本身总共有9个格子，所以顶多有九种颜色，但由于不可能每个格子颜色不一样，所以，当如果格子数较多时，颜色种数肯定是<9的，而k较小的时候，就在k里面找
    for (int i = 1; i <= min(k, 9); ++i) {
        mp3[i] = 0;
    }
    //找要改成什么颜色，将四个格子中颜色出现两次的格子中的颜色记录下来，出现次数越多，越不选，因为要改成其余的颜色才更可能成为颜色种数>=3的四方格
    for (int i = max_x - 1; i <= max_x; ++i) {
        for (int j = max_y - 1; j <= max_y; ++j) {
            if (!in(i, j)) {
                continue;
            }
            if (i == n || j == n) {
                continue;
            }
            mp1.clear();
            for (int r = 0; r < 4; ++r) {
                mp1[g[i + dx[r]][j + dy[r]]]++;
            }
            if (mp1.size() == 2) {
                for (int r = 0; r < 4; r++) {
                    mp3[g[i + dx[r]][j + dy[r]]]++;
                }
            }
        }
    }
    //遍历mp3所记录的目标格子周围的颜色，找出出现次数最少的颜色,修改格子颜色
    for (const auto& t : mp3) {
        if (minn >= t.y) {
            minn = t.y;
            color = t.x;
        }
    }
    g[max_x][max_y] = color;
    //再次重新遍历，记录修改后的种数
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            mp1.clear();
            for (int r = 0; r < 4; ++r) {
                mp1[g[i + dx[r]][j + dy[r]]]++;
            }
            if (mp1.size() >= 3) cnt++;
        }
    }
    //对比修改前后的数目，取较大值
    printf("%d", max(cnt, ans));
    return 0;
}