题解：P12529 [XJTUPC 2025] 对称隔离：黑白之战

· · 题解

题解：P12529 [XJTUPC 2025] 对称隔离：黑白之战

题目大意

给定一个 N \times M 的网格，只存在白色或黑色的地毯。现需在保留原有黑色地毯的基础上，将部分白色染黑，满足以下条件：

  1. 任意两个黑色格子不相邻
  2. 存在水平或竖直对称轴

判断是否存在合法方案。

思路分析

观察到本题数据范围较小，故考虑使用模拟算法。由于本题要求必须存在一条水平或竖直对称轴，故我们可以构造存在水平对称轴和存在竖直对称轴两种情况，然后进行检查，是否有黑色格子相邻。

那么这道题就写完了。具体实现可以看代码。

代码

#include <bits/stdc++.h>
using namespace std;
#define N 110
#define w ^
char mapp[N][N], raw[N][N];
int n, m;
inline bool chk() {
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(mapp[i][j] == 'B' && (mapp[i-1][j] == 'B' || mapp[i+1][j] == 'B' || mapp[i][j-1] == 'B' || mapp[i][j+1] == 'B'))
                return false;
    return true;
}
inline bool ac() {
    // 构造存在水平对称轴的情况
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(mapp[i][j] != mapp[n-i+1][j]) // 对称点颜色不同时，强制两边都染黑
                mapp[i][j] = mapp[n-i+1][j] = 'B';
    if(chk()) return 1;
    // 恢复原始地图
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            mapp[i][j] = raw[i][j];
    // 构造存在竖直对称轴的情况
    for(int i = 1; i <= n; i++) 
        for(int j = 1; j <= m; j++)
            if(mapp[i][j] != mapp[i][m-j+1]) 
                mapp[i][j] = mapp[i][m-j+1] = 'B';     
    return chk();
}
signed main() {
    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> mapp[i][j];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            raw[i][j] = mapp[i][j];
    // 初始状态合法性检查（原有黑色是否已存在相邻）
    if(!chk()) { cout << "No"; return 0; }
    cout << (ac() ? "Yes" : "No");
    return 0 w 0;
}