P9820 [ICPC2020 Shanghai R] Mine Sweeper II

Vct14 · 2023-11-06 13:19:55 · 题解

题目大意

给定两张 n\times m 的扫雷地图 A 和 B，请你改变 B 图中的 \lfloor \dfrac{nm}{2} \rfloor 个格子，使两张图上的非地雷格上的数字（周围 8 个格子中的地雷数）之和相同。若有解，输出修改后的 B 图；若无解，输出 -1。

结论

定义一个图 X 的“反地图”为将 X 中的地雷格替换为非地雷格，非地雷格替换为地雷格的扫雷地图 X_2。

将 B 改为 A 或 A 的反地图 A_2 即可。没有无解的情况。

证明

对于相邻的两个格子：

• 若其中一个为地雷格，另外一个为非地雷格，则它的贡献为 1，反转后的贡献也为 1，所以它们的贡献相同。
• 若两个格子相同，则它们的贡献均为 0，也相同。

综上，任意两个相邻的格子都可以取反，取反后贡献不变。

因此，A 或 A 的反地图 A_2 两张图上的非地雷格上的数字之和相同。

2. 将 B 改为 A 或 A 的反地图 A_2 所需的修改次数不大于 \lfloor \dfrac{nm}{2} \rfloor。

设 A 和 B 有 k 个格子不同，即将 B 改为 A 需要修改 k 次：

因为 A 与 A_2 所有格子都不同，所以 B 与 A_2 有 nm-k 个格子不同，需要修改 nm-k 次。

那么题目可化为证明 k 和 nm-k 中必有一数不大于 \lfloor \dfrac{nm}{2} \rfloor。这是显然的。

所以将 B 改为 A 或 A 的反地图 A_2 所需的修改次数不大于 \lfloor \dfrac{nm}{2} \rfloor。

代码

#include<bits/stdc++.h>
using namespace std;

int getbomb(){
    char bomb;
    cin>>bomb;
    if(bomb=='X') return 1;
    else return 0;
} 

void outbomb(bool b){
    if(b) cout<<"X";
    else cout<<".";
}

bool a[1002][1002];

int main(){
    int n,m;
    cin>>n>>m;
    int k=0;
    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) a[i][j]=getbomb();
    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) if(getbomb()!=a[i][j]) k++;
    if(k<=n*m/2){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++) outbomb(a[i][j]);
            cout<<"\n";
        }
    } 
    else{
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++) outbomb(!a[i][j]);
            cout<<"\n";
        }
    } 
    return 0;
}