给两个偶数 \(n\) 和 \(m\) 。任务是构造任意一个二进制矩阵，\(n \times m\) 。对于任意 \((i, j)\) ，有且仅有两个邻居的颜色与 \(a_{i, j}\) 不同。邻居的定义为 \(|x - x'| + |y - y'| = 1\) 。
观察：任何 \(n \times m\) 的矩阵若作为一个大型矩阵的子矩阵不会受到限制。于是构造大型矩阵。
性质1： 矩阵、网格构造性问题由小及大考虑。
- 矩阵大小 \(1 \times 1\) 。
- 矩阵大小为 \(2 \times 2\)
和它的旋转矩阵，是唯一合法构造。
- 矩阵大小为 \(4 \times 4\) ，构造题遵守稳定性原则，较优的方案是对 \(2 \times 2\) 的矩阵经过旋转拼接成 \(4 \times 4\) 。由于可控性强，不难枚举出以下构造合法。
-
矩阵大小为 \(8 \times 8\)
强可控性下不难得到，将 \(4\) 个构造出的 \(4 \times 4\) 矩阵直接拼接即可合法。 -
矩阵大小 \(2^x \times 2^x, (x \geq 2)\) ，推广使用四个 \(2^{x-1} \times 2^{x-1}\) 的矩阵拼接。
-
不难观察到只有 \(n, m\) 都为偶数时，所构造出的子矩阵才合法。正好满足题意。
- 即大概率奇数情况下是不存在合法情况的。
矩阵生成公式可以从两维独立的角度考虑。
- 列上：\(j \% 4 = {0, 1}\) 时 \(g_{i, j} = 1\) ，否则 \(g_{i, j} = 0\) 。
- 行上：\(i \% 4 = {2, 3}\) 时，\(reverse(g_i.begin, g_i.end)\) 。
view
#include <bits/stdc++.h>
int g[55][55];
void solve() {
int n, m; std::cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
std::cout << g[i][j] << " \n"[j==m];
}
}
}
signed main() {
for (int i = 1; i <= 50 ; i++) {
for (int j = 1; j <= 50; j++) {
if (j % 4 == 1 || j % 4 == 0) g[i][j] = 1;
else g[i][j] = 0;
}
if (i % 4 == 2 || i % 4 == 3) std::reverse(g[i] + 1, g[i] + 50 + 1);
}
int _ = 1; std::cin >> _;
while (_--) solve();
return 0;
}