你谷 link
loj link
提供一种时间复杂度正确的高妙做法。
首先题目有一条隐藏条件是保证 \(n\not\equiv2\pmod3\) 或 \(m\not\equiv2\pmod3\)，需要通过观察数据得到。
我们钦定 \(n\not\equiv2\pmod3\)，如果不满足则沿主对角线翻转使其满足。
接下来我们令 \(a_{i,j}\) 表示原给定数字表格上第 \(i\) 行第 \(j\) 列的值，\((i,j)\) 表示第 \(i\) 行第 \(j\) 列是否有雷。
首先考虑一种特殊情况，\(a_{x,y}+a_{x+1,y+1}-a_{x,y+1}-a_{x+1,y}=(x-1,y-1)+(x+2,y+2)-(x-1,y+2)-(x+2,y-1)\)，即对于一个 \(2\times2\) 的方格，若我们已知其三个角，我们可以直接求得另外一个角。
思路非常巧妙，首先确定第 \(3\) 行。
利用前面的特殊情况可以递推求出所有 \((3,3k)\)，接下来求别的，需要对 \(m\) 分类讨论。
若 \(m\not\equiv2\pmod3\)，我们将整个图水平翻转，再做一遍，则第三行任意三个相邻的位置只有一个未知，可以直接求。
若 \(m\equiv2\pmod3\)，此时我们将第三行中所有未知的位置取出来排成一列，任意两个相邻位置的和都是已知的，若有 \(2\) 或 \(0\)，两个就都确定了，若全都是 \(1\)，则我们发现任意两个相邻的位置里只要有一个雷就好了，所以直接任意确定一组没有关系。
以此类推，当第 \(3\) 行已知后，将第 \(3\) 行对全图的影响消去，第 \(6\) 行的情况就等价于原来的第三行，以此类推求得所有第 \(3k\) 行。
因为保证了 \(n\not\equiv2\pmod3\)，竖直翻转后重新求一遍则所有未知行两两之间隔了两行，不会互相影响，即可以独立求。
求一个 \(1\times m\) 的矩阵非常简单，直接和上面求第 \(3\) 行类似做就好了。
最佳实现时间复杂度是 \(\mathcal O\left(nm\right)\)。
实现上因为全图翻转是 \(\mathcal O\left(nm\right)\) 的，所以上面讲到做第 \(3\) 行时翻转，实际上不能做一次翻一次，时间复杂度会退化，因为上面讲到特殊情况中有影响的实际上只有四个顶点，那么只要全部一起做就可以只反翻转一次。
细节较多，一个比较好的实现是每确定一个雷就将它在图中的影响消去，写起来会相对简单。
c++ 代码
#include<bits/stdc++.h>using namespace std;#define Reimu inline void // 灵梦赛高
#define Marisa inline int // 魔理沙赛高
#define Sanae inline bool // 早苗赛高
#define Reisen inline LL // 铃仙赛高typedef long long LL;
typedef unsigned long long ULL;
typedef __int128 Suika;inline ostream &operator<<(ostream &cout, Suika x) {static const LL LIM = 1e18;return x < LIM ? cout << LL(x) : cout << LL(x / LIM) << setw(18) << setfill('0') << LL(x % LIM);
}typedef pair<int, int> Pii;
typedef tuple<int, int, int> Tiii;
#define fi first
#define se second#define all(vec) vec.begin(), vec.end()
#define TY(type) const type&template<typename Ty>
Reimu clear(Ty &x) { Ty().swap(x); }const int N = 610;int n, m, revFlg;
int fr[3], fc[3];
char s[N];
int a[N][N], b[N][N];Reimu swp(int i1, int j1, int i2, int j2) { swap(a[i1][j1], a[i2][j2]); swap(b[i1][j1], b[i2][j2]); }Reimu reverse1() {int mx = max(n, m);swap(n, m);for (int i = 1; i <= mx; ++i) {for (int j = 1; j < i; ++j) {swp(i, j, j, i);}}
}
Reimu reverse2() {for (int i = 1; i <= n >> 1; ++i) {for (int j = 1; j <= m; ++j) {swp(i, j, n - i + 1, j);}}
}
Reimu reverse3() {for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m >> 1; ++j) {swp(i, j, i, m - j + 1);}}
}#define safe(i, j) ((i) > 0 && (i) <= n && (j) > 0 && (j) <= m)#define set set_
Reimu set(int x, int y, int o) {if (!o) return;b[x][y] = 1;for (int i: {x - 1, x, x + 1}) for (int j: {y - 1, y, y + 1}) if (safe(i, j)) --a[i][j];
}Reimu solve1() {auto calc1 = [&](int i) { for (int j = 3; j <= m; j += 3) set(i, j, a[i - 2][j - 2] + a[i - 1][j - 1] - a[i - 2][j - 1] - a[i - 1][j - 2]); };for (int i = 3; i <= n; i += 3) calc1(i);if (fc[0]) {reverse3();for (int i = 3; i <= n; i += 3) calc1(i);reverse3();for (int i = 3; i <= n; i += 3) {for (int j = 1; j <= m; ++j) if (!fc[j % 3]) {set(i, j, a[i - 1][j] - a[i - 2][j]);}}return;}auto calc2 = [&](int i) {for (int j = 0; j <= m; j += 3) {if (j) do {int t = a[i - 1][j] - a[i - 2][j];if (t & 1) continue;t >>= 1; set(i, j - 1, t); set(i, j + 1, t);for (int k = j - 2; k > 0; --k) if (k % 3) set(i, k, a[i - 1][k + 1] - a[i - 2][k + 1]);for (int k = j + 2; k <= m; ++k) if (k % 3) set(i, k, a[i - 1][k - 1] - a[i - 2][k - 1]);return;} while (false);int t = a[i - 1][j + 1] - a[i - 2][j + 1];if (t & 1) continue;t >>= 1; set(i, j + 1, t); set(i, j + 2, t);for (int k = j - 1; k > 0; --k) if (k % 3) set(i, k, a[i - 1][k + 1] - a[i - 2][k + 1]);for (int k = j + 4; k <= m; ++k) if (k % 3) set(i, k, a[i - 1][k - 1] - a[i - 2][k - 1]);return;}for (int j = 0; j <= m; j += 3) set(i, j + 1, 1);};for (int i = 3; i <= n; i += 3) calc2(i);
}
Reimu solve2() {auto calc1 = [&](int i) { for (int j = 3; j <= m; j += 3) set(i, j, a[i][j - 1] - a[i][j - 2]); };for (int i = 1; i <= n; ++i) if (!fr[i % 3]) calc1(i);if (fc[0]) {reverse3();for (int i = 1; i <= n; ++i) if (!fr[i % 3]) calc1(i);reverse3();for (int i = 1; i <= n; ++i) if (!fr[i % 3]) {for (int j = 1; j <= m; ++j) if (!fc[j % 3]) {set(i, j, a[i][j]);}}return;}auto calc2 = [&](int i) {for (int j = 0; j <= m; j += 3) {if (j) do {int t = a[i][j];if (t & 1) continue;t >>= 1; set(i, j - 1, t); set(i, j + 1, t);for (int k = j - 2; k > 0; --k) if (k % 3) set(i, k, a[i][k + 1]);for (int k = j + 2; k <= m; ++k) if (k % 3) set(i, k, a[i][k - 1]);return;} while (false);int t = a[i][j + 1];if (t & 1) continue;t >>= 1; set(i, j + 1, t); set(i, j + 2, t);for (int k = j - 1; k > 0; --k) if (k % 3) set(i, k, a[i][k + 1]);for (int k = j + 4; k <= m; ++k) if (k % 3) set(i, k, a[i][k - 1]);return;}for (int j = 0; j <= m; j += 3) set(i, j + 1, 1);};for (int i = 1; i <= n; ++i) if (!fr[i % 3]) calc2(i);
}
Reimu solve() {solve1(); reverse2();solve1(); reverse2();solve2();
}int main() {ios::sync_with_stdio(false); cin.tie(nullptr);cin >> n >> m;for (int i = 1; i <= n; ++i) {cin >> s + 1;for (int j = 1; j <= m; ++j) a[i][j] = s[j] & 15;}if (n % 3 == 2) revFlg = 1, reverse1();fr[0] = fc[0] = 1; fr[(n + 1) % 3] ^= 1; fc[(m + 1) % 3] ^= 1;solve();if (revFlg) reverse1();for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) cout << ".X"[b[i][j]];cout << '\n';}return 0;
}
