CF1551D2 Domino (hard version)

本题与 D1 唯一的区别在于，D1 不需要给出构造答案的方法，而本题需要你给出具体的构造方式。 有一个 $n \times m$ 的表格（$n$ 行 $m$ 列）。保证 $n \cdot m$ 是偶数。 一个多米诺骨牌由两个有公共边的格子组成。它可以是水平放置（两个格子左右相邻），也可以是竖直放置（两个格子上下相邻）。 你需要在表格上放置 $\frac{nm}{2}$ 个多米诺骨牌，使得恰好有 $k$ 个是水平放置，其余的都是竖直放置。多米诺骨牌不能重叠，且必须完全覆盖整个表格。

第一行包含一个整数 $t$（$1 \le t \le 10$），表示测试用例的数量。接下来有 $t$ 组测试数据。 每组测试数据包含一行，包含三个整数 $n$、$m$、$k$（$1 \le n, m \le 100$，$0 \le k \le \frac{nm}{2}$，$n \cdot m$ 是偶数），分别表示行数、列数和水平多米诺骨牌的数量。

对于每个测试用例： - 如果无法按照要求放置多米诺骨牌，输出一行 "NO"（不带引号）。 - 否则，先输出一行 "YES"，然后输出 $n$ 行，每行包含 $m$ 个小写拉丁字母，表示表格的布局。每个格子用一个字母标记，要求对于每两个有公共边的格子，只有当它们属于同一个多米诺骨牌时才用相同的字母标记。也就是说，同一个多米诺骨牌的两个格子要用相同的字母标记，且相邻的两个多米诺骨牌不能用相同的字母标记。如果有多种方案，输出任意一种即可。

由 ChatGPT 4.1 翻译