P9820 [ICPC 2020 Shanghai R] Mine Sweeper II

题目描述

扫雷地图 $X$ 可以表示为一个 $n\times m$ 的网格。网格中的每个单元格要么是地雷单元格，要么是非地雷单元格。地雷单元格上没有数字。每个非地雷单元格有一个数字，表示其周围地雷单元格的数量。（如果一个单元格与另一个单元格共享至少一个公共点，则它们是相邻的。因此，每个不在边界上的单元格周围有 $8$ 个单元格。）以下是一个 $16\times 30$ 的扫雷地图，其中标记的单元格表示地雷单元格，空白单元格表示数字为 0 的非地雷单元格。

给定两个大小为 $n\times m$ 的扫雷地图 $A,B$，你应该在 $B$ 中修改最多 $ \left\lfloor \frac{nm}{2} \right\rfloor $（即小于或等于 $\frac{nm}{2}$ 的最大非负整数）个单元格（从非地雷单元格变为地雷单元格或反之），使得 $A$ 中非地雷单元格的数字之和与 $B$ 中非地雷单元格的数字之和相同。（如果地图中没有非地雷单元格，则和被视为 $0$。）

如果存在多个解，输出其中任意一个。如果不存在解，输出一行 -1。

输入格式

第一行包含两个整数 $n,m(1\le n,m\le 1000)$，表示给定的扫雷地图的大小。

接下来的 $n$ 行的第 $i$ 行包含一个长度为 $m$ 的字符串，由 . 和 X 组成，表示扫雷地图 $A$ 的第 $i$ 行。. 表示非地雷单元格，X 表示地雷单元格。

接下来的 $n$ 行的第 $i$ 行包含一个长度为 $m$ 的字符串，由 . 和 X 组成，表示扫雷地图 $B$ 的第 $i$ 行。. 表示非地雷单元格，X 表示地雷单元格。

输出格式

如果不存在解，输出一行 -1。

否则，输出 $n$ 行表示修改后的扫雷地图 $B$。第 $i$ 行应包含一个长度为 $m$ 的字符串，由 . 和 X 组成，表示修改后的地图 $B$ 的第 $i$ 行。. 表示非地雷单元格，X 表示地雷单元格。

请注意，您不需要输出非地雷单元格上的数字，因为这些数字可以通过输出的扫雷地图确定。

输入输出样例 #1

输入 #1

2 4
X..X
X.X.
X.X.
.X..

输出 #1

X.XX
.X..

说明/提示

我们在 $B$ 中修改一个单元格。然后 $A$ 和 $B$ 中非地雷单元格上的数字之和都等于 10。

题面翻译由 ChatGPT-4o 提供。

C++实现

#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;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容