#2239. 赤红

    ID: 2239 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>TEAM赛事:contest2022来源:qoj.ac数据:公开样例分块

赤红

赤红

题目描述

标题: 赤红 - Problem - QOJ.ac

#11001. 赤红

Statistics

The problem was used in the following contests:

题目描述

小 L 建立了一个都是彩色房屋的社区!

今天他在社区散步时注意到某些颜色重复过多,因此他决定制定城市规划方案来优化房屋颜色分布。

社区被建模为 N×M 的网格,每个单元格代表一栋房屋。要求任意两栋曼哈顿距离小于 D 的房屋必须涂不同颜色(曼哈顿距离:|i1−i2|+|j1−j2|)。

他希望最小化使用的颜色数量(因为订购多种颜料成本高昂)。请帮助设计一个着色方案,使得:

  1. 使用的颜色数量 K 最少
  2. 输出具体着色方案(颜色用 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