#P17685. [2026年保加利亚]Gardening

[2026年保加利亚]Gardening

题目描述

Azusa 想和她的朋友 Laika 一起通过园艺来娱乐。

她们想建造一座长为 NN 米、宽为 MM 米的矩形花园。花园被划分成 N×MN\times M 个大小为 11 米 ×\times 11 米的小方格。

Laika 找到了 KK 种不同的花。Azusa 和 Laika 会在每一个小方格中种植恰好一种花。

出于美观方面的考虑,整个花园必须同时满足下面三个条件。

条件 1

每一种花都必须在花园中至少出现一次。

条件 2

对于任意两个种植了同一种花的方格,它们之间必须存在一条路径,使得路径经过的所有方格都种植这种花。

这里,一条路径是由若干个相邻方格组成的序列。

换句话说,对于每一种花,所有种植这种花的方格在四联通意义下必须构成一个连通块。

条件 3

每一个方格都必须恰好有 两个 与它相邻、并且种植了同一种花的方格。

两个方格当且仅当它们拥有一条公共边时才称为相邻;仅仅共用一个顶点不算相邻。


给定 TT 组不同的 N,M,KN,M,K。

对于每一组测试数据,请构造一个满足上述所有条件的花园;如果不存在这样的花园,则判断其无解。

输入格式

第一行包含一个整数:

T

表示测试用例数量。

接下来 TT 行,每行包含三个整数:

N M K

描述一个测试用例。

输出格式

按照输入顺序依次输出每个测试用例的答案。

如果不存在合法花园,输出:

NO

如果存在合法花园,首先输出:

YES

然后输出一个 N×MN\times M 的整数矩阵。

矩阵第 ii 行第 jj 列的整数表示花园中对应方格种植的花的种类。

花的种类编号必须属于:

1,2,…,K.1,2,\ldots,K.

如果存在多个合法方案,可以输出任意一个。

数据范围

  • 1≤T≤1000001\le T\le100000
  • 1≤N,M≤5001\le N,M\le500
  • 1≤K≤N×M1\le K\le N\times M

此外,定义 SS 为所有存在合法答案的测试用例的 N×MN\times M 之和,则保证:

S≤200000.S\le200000.

子任务

子任务 分值 依赖子任务 NN MM 其他限制
0 — — 样例
1 5 ≤4\le4 ≤4\le4 —
2 6 0–1 —
3 10 0–2 ≤6\le6
4 18 — — S≤200000, N=MS\le200000,\ N=M
5 39 ≤500\le500 S≤200000S\le200000,KK 在 [1,NM][1,NM] 中均匀随机选择
6 22 0–5 — 无额外限制

只有通过某个子任务的全部测试,并且通过它所依赖的全部子任务,才能获得该子任务的分数。

样例

输入

5
2 2 2
2 2 1
4 4 4
4 4 2
4 6 3

一种合法输出

NO
YES
1 1
1 1
YES
1 1 2 2
1 1 2 2
3 3 4 4
3 3 4 4
YES
1 1 1 1
1 2 2 1
1 2 2 1
1 1 1 1
YES
1 1 1 1 1 1
1 2 2 3 3 1
1 2 2 3 3 1
1 1 1 1 1 1

样例说明

对于第一组测试数据,无法在 2×22\times2 的花园中使用恰好 22 种花并同时满足全部条件,因此输出 NO。

其余测试数据均存在合法构造,样例输出给出了其中一种可能的方案。


难度筛选说明

TS2. Palindromes(回文)