构造

构造 - Mine Sweeper II - ICPC 2020 上海

题意：

给 定 两 个 n × m 的 由 ′ X ′ 和 ′ . ′ 矩 阵 A 和 B ， 表 示 两 个 扫 雷 的 矩 阵 ， 给定两个n×m的由'X'和'.'矩阵A和B，表示两个扫雷的矩阵， 给定两个n×m的由′X′和′.′矩阵A和B，表示两个扫雷的矩阵，

′ X ′ 表 示 雷 ， ′ . ′ 表 示 空 地 ， 'X'表示雷，'.'表示空地， ′X′表示雷，′.′表示空地，

在 扫 雷 游 戏 中 ， 每 个 空 地 会 有 一 个 数 字 ， 表 示 周 围 8 个 方 向 雷 的 数 量 。 在扫雷游戏中，每个空地会有一个数字，表示周围8个方向雷的数量。 在扫雷游戏中，每个空地会有一个数字，表示周围8个方向雷的数量。

对 于 矩 阵 A 和 B ， 各 个 空 地 的 数 字 之 和 ， 记 为 W A 和 W B 。 对于矩阵A和B，各个空地的数字之和，记为W_A和W_B。 对于矩阵A和B，各个空地的数字之和，记为WA​和WB​。

试 问 ， 能 否 对 矩 阵 B 进 行 不 超 过 ⌊ n ⋅ m 2 ⌋ 次 操 作 ， 每 次 操 作 可 以 将 一 个 ′ X ′ ( ′ . ′ ) 变 成 ′ . ′ ( ′ X ′ ) ， 试问，能否对矩阵B进行不超过\lfloor\frac{n·m}{2}\rfloor次操作，每次操作可以将一个'X'('.')变成'.'('X')， 试问，能否对矩阵B进行不超过⌊2n⋅m​⌋次操作，每次操作可以将一个′X′(′.′)变成′.′(′X′)，

使 得 W B = W A 。 使得W_B=W_A。 使得WB​=WA​。

如 果 不 能 ， 输 出 − 1 。 如果不能，输出-1。 如果不能，输出−1。

输入：

首 行 包 括 两 个 正 整 数 n 和 m ( 0 ≤ n , m ≤ 1000 ) ， 首行包括两个正整数n和m(0\le n,m\le 1000)， 首行包括两个正整数n和m(0≤n,m≤1000)，

接 着 2 个 n × m 的 矩 阵 ， 表 示 A 和 B 接着2个n×m的矩阵，表示A和B 接着2个n×m的矩阵，表示A和B

输出：

一 个 n × m 的 矩 阵 ， 表 示 修 改 后 的 矩 阵 。 一个n×m的矩阵，表示修改后的矩阵。 一个n×m的矩阵，表示修改后的矩阵。

若 有 解 ， 输 出 任 意 一 组 。 否 则 输 出 − 1 。 若有解，输出任意一组。否则输出-1。 若有解，输出任意一组。否则输出−1。

示例1
输入

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

输出

X.XX
.X..

---

分析：

本 题 有 一 个 很 重 要 的 性 质 ： 本题有一个很重要的性质： 本题有一个很重要的性质：

将 一 个 矩 阵 M 的 ′ X ′ 和 ′ . ′ 对 换 ， 矩 阵 M 的 权 置 W M 不 变 。 将一个矩阵M的'X'和'.'对换，矩阵M的权置W_M不变。 将一个矩阵M的′X′和′.′对换，矩阵M的权置WM​不变。

证明：

我 们 考 虑 对 一 个 ′ X ′ 进 行 操 作 ， 那 么 它 将 会 变 成 一 个 ′ . ′ ， 我们考虑对一个'X'进行操作，那么它将会变成一个'.'， 我们考虑对一个′X′进行操作，那么它将会变成一个′.′，

假 设 它 周 围 8 个 方 向 ′ X ′ 的 数 量 为 c n t 1 ， ′ . ′ 的 数 量 为 c n t 2 假设它周围8个方向'X'的数量为cnt_1，'.'的数量为cnt_2 假设它周围8个方向′X′的数量为cnt1​，′.′的数量为cnt2​

那 么 本 次 操 作 将 会 使 得 权 置 增 加 c n t 1 ， 减 少 c n t 2 ， 即 权 置 改 变 c n t 1 − c n t 2 那么本次操作将会使得权置增加cnt_1，减少cnt_2，即权置改变cnt_1-cnt_2 那么本次操作将会使得权置增加cnt1​，减少cnt2​，即权置改变cnt1​−cnt2​

同 理 ， 如 果 我 们 对 ′ . ′ 进 行 操 作 ， 权 置 将 改 变 c n t 2 − c n t 1 。 同理，如果我们对'.'进行操作，权置将改变cnt_2-cnt_1。 同理，如果我们对′.′进行操作，权置将改变cnt2​−cnt1​。

如 下 图 ： 如下图： 如下图：

如 果 我 们 对 蓝 色 的 点 操 作 ， 那 么 它 所 能 影 响 到 的 点 的 范 围 应 当 是 绿 色 的 点 ， 对 隔 一 层 的 点 不 会 产 生 影 响 。 如果我们对蓝色的点操作，那么它所能影响到的点的范围应当是绿色的点，对隔一层的点不会产生影响。 如果我们对蓝色的点操作，那么它所能影响到的点的范围应当是绿色的点，对隔一层的点不会产生影响。

为 了 方 便 ， 假 设 蓝 色 点 是 ′ X ′ ， 修 改 它 产 生 的 贡 献 为 c n t 1 − c n t 2 ， 为了方便，假设蓝色点是'X'，修改它产生的贡献为cnt_1-cnt_2， 为了方便，假设蓝色点是′X′，修改它产生的贡献为cnt1​−cnt2​，

此 时 我 们 将 绿 色 的 一 层 点 全 部 变 反 ， 则 ′ X ′ 周 围 的 ′ X ′ 数 量 将 变 为 c n t 2 ， ′ . ′ 的 数 量 将 变 成 c n t 1 ， 此时我们将绿色的一层点全部变反，则'X'周围的'X'数量将变为cnt_2，'.'的数量将变成cnt_1， 此时我们将绿色的一层点全部变反，则′X′周围的′X′数量将变为cnt2​，′.′的数量将变成cnt1​，

此 时 将 会 产 生 c n t 2 − c n t 1 的 贡 献 ， 此时将会产生cnt_2-cnt_1的贡献， 此时将会产生cnt2​−cnt1​的贡献，

因 此 ， 和 的 贡 献 为 ( c n t 1 − c n t 2 ) + ( c n t 2 − c n t 1 ) = 0 。 因此，和的贡献为(cnt_1-cnt_2)+(cnt_2-cnt_1)=0。 因此，和的贡献为(cnt1​−cnt2​)+(cnt2​−cnt1​)=0。

所 以 ， 我 们 能 够 得 出 结 论 。 所以，我们能够得出结论。 所以，我们能够得出结论。

接下来

对 于 每 一 个 矩 阵 B ， 我 们 首 先 考 虑 能 否 将 B 直 接 修 改 成 A 。 对于每一个矩阵B，我们首先考虑能否将B直接修改成A。 对于每一个矩阵B，我们首先考虑能否将B直接修改成A。

当 矩 阵 A 和 矩 阵 B 不 相 同 的 点 的 数 量 ≤ ⌊ n ⋅ m 2 ⌋ 时 ， 我 们 可 以 这 样 构 造 。 当矩阵A和矩阵B不相同的点的数量\le \lfloor\frac{n·m}{2}\rfloor时，我们可以这样构造。 当矩阵A和矩阵B不相同的点的数量≤⌊2n⋅m​⌋时，我们可以这样构造。

当 不 相 同 的 点 的 数 量 > ⌊ n ⋅ m 2 ⌋ 时 ， 当不相同的点的数量> \lfloor\frac{n·m}{2}\rfloor时， 当不相同的点的数量>⌊2n⋅m​⌋时，

利 用 上 述 结 论 ， 我 们 可 以 把 B 变 换 成 A 的 ′ ′ 反 ′ ′ 矩 阵 ， 即 将 A 的 所 有 ′ X ′ 变 成 ′ . ′ ， 所 有 ′ . ′ 变 成 ′ X ′ ， 利用上述结论，我们可以把B变换成A的''反''矩阵，即将A的所有'X'变成'.'，所有'.'变成'X'， 利用上述结论，我们可以把B变换成A的′′反′′矩阵，即将A的所有′X′变成′.′，所有′.′变成′X′，

这 样 的 矩 阵 。 此 时 不 同 点 的 数 量 将 会 ≤ ⌊ n ⋅ m 2 ⌋ 。 这样的矩阵。此时不同点的数量将会\le \lfloor\frac{n·m}{2}\rfloor。 这样的矩阵。此时不同点的数量将会≤⌊2n⋅m​⌋。

代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>using namespace std;const int N = 1010;
int n, m;
char A[N][N], B[N][N];int main()
{scanf("%d%d",&n,&m);for(int i=0;i<n;i++) scanf("%s",A[i]);for(int i=0;i<n;i++) scanf("%s",B[i]);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++) printf("%s\n",A[i]);elsefor(int i=0;i<n;i++){for(int j=0;j<m;j++)if(A[i][j]=='.') putchar('X');else putchar('.');puts("");}return 0;
}