#P18448. Puzzle: Question Mark

Puzzle: Question Mark

Puzzle: Question Mark

输入:标准输入;输出:标准输出。

XingHui 是一位拼图高手。今天她正在玩一个叫作 Filling with Question Marks 的拼图游戏。

游戏包含一个 nn 行、nn 列的网格,以及若干块问号形拼图(简称 QM 拼图)。每块 QM 拼图占据四个格子,形状如下:

一块原题 QM 拼图

为避免对图形的歧义,也可以用相对格坐标表示这一基本形状:

(0,0),(0,1),(1,1),(2,0).(0,0),(0,1),(1,1),(2,0).

每块拼图必须完全放在网格内;允许旋转任意 9090 度的整数倍,也允许翻面。因此恰有下图所示的八种朝向:

原题允许的八种旋转与翻转形状

任意两块拼图不能占据同一个格子。目标是在 n×nn\times n 网格内放入尽可能多的 QM 拼图。

XingHui 想知道你能否完成这个任务。请输出能放入的最大拼图数量,以及一种达到最大值的摆放方案。

输入格式

第一行包含整数 TT,表示测试用例数。

每个测试用例仅包含一行,一个整数 nn(1≤n≤2×1031\le n\le2\times10^3)。

保证一个输入文件内,所有测试用例的 n2n^2 之和不超过 5×1065\times10^6。

输出格式

对于每个测试用例:

首先输出一行,一个整数 kk,表示可以放入的最大 QM 拼图数量。

然后输出 nn 行,每行 nn 个整数。第 ii 行第 jj 个整数 ai,ja_{i,j} 表示该格属于第几块拼图:ai,j=0a_{i,j}=0 表示空格,否则为 1..k1..k 中的一个编号。每个拼图编号应恰好出现四次,且这四格必须构成允许的一种 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

原样例说明

两个原样例的摆放方案如下。相同颜色表示同一块拼图,白色表示未覆盖的格子。

原题 n=3 与 n=4 的样例摆放