自动搬运

查看原文

来自洛谷，原作者为

	_hud Hi

搬运于2025-08-24 23:16:14，当前版本为作者最后更新于2025-05-19 15:03:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解：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;
}