#P18448. Puzzle: Question Mark
Puzzle: Question Mark
Puzzle: Question Mark
输入:标准输入;输出:标准输出。
XingHui 是一位拼图高手。今天她正在玩一个叫作 Filling with Question Marks 的拼图游戏。
游戏包含一个 行、 列的网格,以及若干块问号形拼图(简称 QM 拼图)。每块 QM 拼图占据四个格子,形状如下:

为避免对图形的歧义,也可以用相对格坐标表示这一基本形状:
每块拼图必须完全放在网格内;允许旋转任意 度的整数倍,也允许翻面。因此恰有下图所示的八种朝向:

任意两块拼图不能占据同一个格子。目标是在 网格内放入尽可能多的 QM 拼图。
XingHui 想知道你能否完成这个任务。请输出能放入的最大拼图数量,以及一种达到最大值的摆放方案。
输入格式
第一行包含整数 ,表示测试用例数。
每个测试用例仅包含一行,一个整数 ()。
保证一个输入文件内,所有测试用例的 之和不超过 。
输出格式
对于每个测试用例:
首先输出一行,一个整数 ,表示可以放入的最大 QM 拼图数量。
然后输出 行,每行 个整数。第 行第 个整数 表示该格属于第几块拼图: 表示空格,否则为 中的一个编号。每个拼图编号应恰好出现四次,且这四格必须构成允许的一种 QM 形状。
如果最优摆放方案不唯一,输出任意一种即可。
原题特别要求:每行末尾不要输出多余空格,否则可能被判为不正确。
原样例
2
3
4
2
0 1 1
2 2 1
2 1 2
4
1 1 2 2
1 2 3 2
4 1 4 3
4 4 3 3
原样例说明
两个原样例的摆放方案如下。相同颜色表示同一块拼图,白色表示未覆盖的格子。
