Mine Sweeper II

题目描述

A mine-sweeper map $X$ can be expressed as an $n\times m$ grid. Each cell of the grid is either a mine cell or a non-mine cell. A mine cell has no number on it. Each non-mine cell has a number representing the number of mine cells around it. (A cell is around another cell if they share at least one common point. Thus, every cell that is not on the boundary has $8$ cells around it.) The following is a $16\times 30$ mine-sweeper map where a flagged cell denotes a mine cell and a blank cell denotes a non-mine cell with number 0.

Given two mine-sweeper maps $A,B$ of size $n\times m$, you should modify at most $\lfloor \frac{nm}{2}\rfloor$ (i.e. the largest nonnegative integer that is less than or equal to $\frac{nm}{2}$) cells in $B$ (from a non-mine cell to a mine cell or vice versa) such that the sum of numbers in the non-mine cells in $A$ and the sum of numbers in the non-mine cells in $B$ are the same. (If a map has no non-mine cell, the sum is considered as $0$.)

If multiple solutions exist, print any of them. If no solution exists, print “-1” in one line.

输入描述

The first line contains two integers $n,m(1\le n,m\le 1000)$, denoting the size of given mine-sweeper maps.

The $i$-th line of the following $n$ lines contains a length-$m$ string consisting of “.” and “X” denoting the $i$-th row of the mine-sweeper map $A$. A “.” denotes for a non-mine cell and an “X” denotes for a mine cell.

The $i$-th line of the following $n$ lines contains a length-$m$ string consisting of “.” and “X” denoting the $i$-th row of the mine-sweeper map $B$. A “.” denotes for a non-mine cell and an “X” denotes for a mine cell.

输出描述

If no solution exists, print “-1” in one line.

Otherwise, print $n$ lines denoting the modified mine-sweeper map $B$. The $i$-th line should contain a length-$m$ string consisting of “.” and “X” denoting the $i$-th row of the modified map $B$. A “.” denotes for a non-mine cell and an “X” denotes for a mine cell.

Please notice that you need not print the numbers on non-mine cells since these numbers can be determined by the output mine-sweeper map.

题面翻译

扫雷地图有 n 行 m 列。每个格子是地雷或者空地。每个空地显示一个数字，数字代表周围 8 个格子中是地雷的格子的数量。你可以在一次操作中，将一个地雷修改为空地，或者将一个空地修改为地雷。给定两张扫雷地图 A 和 B，请对 B 进行不超过 $\lfloor \frac{nm}{2}\rfloor$ 次操作，使得 B 地图所有空地上的数字之和等于 A 地图所有空地上的数字之和。

样例 #1

样例输入 #1

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

样例输出 #1

X.XX
.X..

思路

考虑两种方案。方案一：将 B 改为 A。方案二：将 B 改成 A 的相反，即对应位置若 A 为地雷则改后的 B 为空地，反之改后的B为地雷。对于每个格子的修改，都恰好存在于两种方案之一。所以两种方案的操作次数之和为 $nm$。根据鸽巢原理，在两种方案中，一定存在一种方案的操作次数不超过 $\lfloor \frac{nm}{2}\rfloor$。

代码

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

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    vector<vector<char>> a(n, vector<char>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> a[i][j];
    vector<vector<char>> b(n, vector<char>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> b[i][j];
    // 方案一：将B改成A
    // 方案二：将B改成A的相反，即若A为地雷则改后的B为空地，反之改后的B为地雷
    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++)
                cout << a[i][j];
            cout << '\n';
        }
    }
    else // 如果方案一步数不满足条件，则根据鸽巢原理，方案二一定满足条件
    {
        // 输出方案二的结果
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
                cout << ((a[i][j] == '.') ? 'X' : '.');
            cout << '\n';
        }
    }

    return 0;
}