#2239. 赤红
赤红
赤红
题目描述
标题: 赤红 - Problem - QOJ.ac
#11001. 赤红
The problem was used in the following contests:
题目描述
小 L 建立了一个都是彩色房屋的社区!
今天他在社区散步时注意到某些颜色重复过多,因此他决定制定城市规划方案来优化房屋颜色分布。
社区被建模为 N×M 的网格,每个单元格代表一栋房屋。要求任意两栋曼哈顿距离小于 D 的房屋必须涂不同颜色(曼哈顿距离:|i1−i2|+|j1−j2|)。
他希望最小化使用的颜色数量(因为订购多种颜料成本高昂)。请帮助设计一个着色方案,使得:
- 使用的颜色数量 K 最少
- 输出具体着色方案(颜色用 1 到 K 的整数表示)
输入格式
输入的第一行包含一个整数 T,表示测试用例的数量。每个测试用例的第一行包含三个整数 N、M 和 D,分别表示网格的行数、列数和最小曼哈顿距离限制。
输出格式
对于每个测试用例,首先输出一个整数 K 表示所需的最少颜色数量。
接着输出 N 行,每行包含 M 个用空格分隔的整数,表示网格中每个位置的颜色编号(必须为 1 到 K 之间的整数)。相邻测试用例的输出之间不需要空行。
样例输入
3
3 3 1
2 4 1000
3 3 3
样例输出
1
1 1 1
1 1 1
1 1 1
8
1 2 3 4
5 6 7 8
5
1 2 3
3 4 5
5 1 2
数据范围
对于所有数据,保证 1≤T≤100,1≤N,M≤500,1≤D≤1000。
所有测试用例的 N 总和不超过 500。
所有测试用例的 M 总和不超过 500。
子任务 分值 限制条件 1 8 D=2 2 4 N=1 3 16 D<min(N,M) 4 19 D<max(N,M) 5 24 D>max(N,M) 6 15 N=M 7 14 无特殊限制
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3
3 3 1
2 4 1000
3 3 3
1
1 1 1
1 1 1
1 1 1
8
1 2 3 4
5 6 7 8
5
1 2 3
3 4 5
5 1 2