自动搬运

查看原文

来自洛谷，原作者为

	Vct14 **

搬运于2025-08-24 22:52:07，当前版本为作者最后更新于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. $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;
}