题解：P14108 [ZJCPC 2017] Domino Tiling

· · 题解

首先判掉 n\times m\bmod 2=1 的情况。

经过一些手玩可以发现，下面的构造是合法的：

也就是把四个金字塔形状的东西拼在一起。

但是这只能处理 |n-m|\le 1 的情况。

再经过一些手玩，可以猜测合法的构造一定是把若干个上面的图形拼成一行。

具体地，不妨设 n\le m，我们把 m 写成 m_1+m_2+\cdots+m_k 的形式，使得对于任意 i，都有 |n-m_i|\le 1 ，然后把所有 n\times m_i 的矩形拼起来。

要确定 m_i 的具体值，只需用类似 dp 的方式即可。如果 dp 跑不出来就是无解。

::::info[代码]

#include<bits/stdc++.h>
using namespace std;
const int maxn = 105;
int T, n, m, fl, c;
int lst[maxn];
int a[maxn][maxn];
int p[4];
void heige(int u, int d, int l, int r, int k) {
    if (u > d || l > r) return;
    if (p[k] == 2) {
        for (int i = u; i <= d; i += 2) a[i][r] = a[i + 1][r] = ++c;
        heige(u, d, l, r - 1, (k + 1) % 4);
    }
    if (p[k] == 0) {
        for (int i = u; i <= d; i += 2) a[i][l] = a[i + 1][l] = ++c;
        heige(u, d, l + 1, r, (k + 1) % 4);
    }
    if (p[k] == 3) {
        for (int i = l; i <= r; i += 2) a[d][i] = a[d][i + 1] = ++c;
        heige(u, d - 1, l, r, (k + 1) % 4);
    }
    if (p[k] == 1) {
        for (int i = l; i <= r; i += 2) a[u][i] = a[u][i + 1] = ++c;
        heige(u + 1, d, l, r, (k + 1) % 4);
    }
}
void build1() {
    for (int i = 1; i <= m; i++) lst[i] = -1;
    lst[0] = 0;
    for (int i = 1; i <= m; i++)
        for (int j = i - 2; j >= 0; j -= 2)
            if (abs(i - j - n) <= 1 && lst[j] != -1) lst[i] = j;
    if (lst[m] == -1) {cout << "Impossible!" << '\n'; return;}
    int x = m, pp = 0;
    while (x) {
        if (pp) p[0] = 3, p[1] = 0, p[2] = 2, p[3] = 1;
        else p[0] = 1, p[1] = 0, p[2] = 2, p[3] = 3;
        heige(1, n, lst[x] + 1, x, 0);
        x = lst[x]; pp ^= 1;
    }
}
void build2() {
    for (int i = 1; i <= m + 1; i++) lst[i] = -1;
    lst[0] = lst[1] = 0;
    for (int i = 2; i <= m + 1; i++)
        for (int j = i - 1; j >= 0; j -= 2)
            if (abs(i - j - n) <= 1 && lst[j] != -1) lst[i] = j;
    if (lst[m] == -1 && lst[m + 1] == -1) {cout << "Impossible!" << '\n'; return;}
    int x = (lst[m] == -1 ? m + 1 : m);
    while (x > 1) {
        if (x <= m)
            for (int i = 1; i <= n; i += 2) a[i][x] = a[i + 1][x] = ++c;
        p[0] = 1, p[1] = 3, p[2] = 0, p[3] = 2;
        heige(1, n, lst[x] + 1, x - 1, 0);
        x = lst[x];
    }
    for (int i = 1; i <= n; i += 2) a[i][x] = a[i + 1][x] = ++c;
}
void work() {
    cin >> n >> m; fl = 0; c = 0;
    if (n * m % 2) {cout << "Impossible!" << '\n'; return;}
    if (n > m) swap(n, m), fl = 1;
    for (int i = 0; i <= n + 1; i++)
        for (int j = 0; j <= m + 1; j++)
            a[i][j] = 0;
    if (n % 2 == 1) build1();
    else build2();
    if (a[1][1] == 0) return;
    if (fl == 0)
        for (int i = 1; i <= n; i++, cout << '\n')
            for (int j = 1; j <= m; j++)
                cout << a[i][j] << ' ';
    else
        for (int i = 1; i <= m; i++, cout << '\n')
            for (int j = 1; j <= n; j++)
                cout << a[j][i] << ' ';
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> T;
    while (T--) work();
    return 0;
}

::::