P14108 [ZJCPC 2017] Domino Tiling

Chiaki 有一个 $n \times m$ 的矩形棋盘。她想用多米诺骨牌（即 $2 \times 1$ 的矩形骨牌）铺满整个棋盘，要求满足： - 棋盘上的每一个格子都被覆盖，且任何两个骨牌不能重叠或部分跨出棋盘。 - 不能存在四个不同骨牌的角同时相交的点。 下图展示了一些不允许出现的排布： :::align{center}  ::: 下图展示了两个 $4 \times 4$ 棋盘的合法铺法： :::align{center}  ::: 你还需要为棋盘上的每一张多米诺骨牌编上不同的编号。编号可以从 $1$ 到 $n \times m$ 之间任意选择。

有多组测试数据。输入的第一行为一个整数 $T$，表示测试数据的组数。对于每组数据： 第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 100$），表示矩形棋盘的大小。 保证所有测试用例中 $n \times m$ 的总和不超过 $2 \times 10^6$。

对于每组测试数据，输出一种满足题意要求的棋盘。输出共 $n$ 行，每行 $m$ 个整数。输出中的每个整数代表骨牌的 $id$，相同 $id$ 的格子属于同一张骨牌。 如果无解，则输出 “Impossible!”（不含引号）。

由 ChatGPT 5 翻译