ICPC2020上海B - Mine Sweeper II

思维

[B-Mine Sweeper II_第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（上海）（重现赛）@hzy0227 (nowcoder.com)](https://codeforces.com/gym/103202/problem/I)

题意

在 \(n*m\;(1<=n,m<=1000)\) 的网格中扫雷，雷上没有数字，别的格子上的数字表示以它为中心的九宫格中的雷的个数

给出两个雷图A，B，"X"代表雷，"." 代表没有雷，每次操作可以将 B 中任意一个格子反转（雷变非雷，非雷变雷），求是否可以在 \(\lfloor\frac {n*m}2\rfloor\) 次操作内使 B 的各个格子的数字和 == A 的各个格子的数字和，并给出 B 最终的雷图

思路

思考数字的含义是什么，不完全是一个格子周围的雷的数量，因为如果当前格子是雷的话，他周围的雷对它就没有贡献了

数字的真正含义是相邻的（雷，非雷）对数，因此反转整个图后这个数是不变的

所以可以尝试把 B 直接变成 A，如果次数超了就把 B 变成 A 的反图

代码

#include<bits/stdc++.h>

typedef long long ll;

typedef std::pair<int, int> PII;

#define ALL(x) x.begin(),x.end()

#define pb push_back

#define fi first

#define se second

#define endl '\n'

using namespace std;

const int N = 1e3 + 10;

char a[N][N], b[N][N];

int n, m;

int main() {

	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; i++)

		for (int j = 0; j < m; j++)

			cin >> a[i][j];

	for (int i = 0; i < n; i++)

		for (int j = 0; j < m; j++)

			cin >> b[i][j];

	int cnt = 0;

	for (int i = 0; i < n; i++)

		for (int j = 0; j < m; j++)

			if (a[i][j] != b[i][j])

				cnt++;

	if (cnt > n * m / 2)

	{

		for (int i = 0; i < n; i++)

			for (int j = 0; j < m; j++)

				if (a[i][j] == 'X')

					a[i][j] = '.';

				else

					a[i][j] = 'X';

	}

	for (int i = 0; i < n; i++)

	{

		for (int j = 0; j < m; j++)

			cout << a[i][j];

		cout << endl;

	}

	return 0;

}

巴特西

ICPC2020上海B - Mine Sweeper II

思维

题意

思路

代码

最新文章

热门文章