#P18291. Hexagon Puzzle

Hexagon Puzzle

Hexagon Puzzle

Kotoha 收到一个六边形拼图作为生日礼物。棋盘由 nn 行正六边形组成,第 ii 行恰有 ii 个六边形。对 i>1i>1,第 ii 行的第 jj 个六边形与上一行第 jj 个、第 j−1j-1 个六边形共边,前提是相应格子存在。下图依次展示 n=1,2,3,4n=1,2,3,4 的棋盘。

原题四种棋盘

每块 V 形拼片恰好占据三个六边形,其形状如下。

原题V形拼片

拼片可以旋转 6060 度的整数倍,共有下面六种朝向。拼片有 2626 种颜色,分别用大写英文字母 A 到 Z 表示。

原题六种旋转

请放置尽可能多块 V 形拼片,并输出任意一种最优方案,满足:

  • 每块拼片完全位于棋盘内,恰好占据三个六边形。
  • 不同拼片占据的六边形不重叠。
  • 任何两块相邻拼片的颜色不同。如果两块拼片至少有一对格子共用一条边,就称它们相邻;只接触顶点不算相邻。

输入格式

输入只有一行,包含一个整数 nn,满足 1≤n≤10241≤n≤1024。只有一组数据。

输出格式

输出 nn 行,仅输出方案,不额外输出拼片数量。

第 ii 行(从 11 开始)必须恰好包含 n+i−1n+i-1 个字符:先输出 n−in-i 个 ASCII 空格,再输出本行 ii 个格子的字符,相邻两个格子字符之间恰好有一个 ASCII 空格。

格子未被覆盖时输出点号 .;否则输出覆盖它的拼片的颜色,即一个大写英文字母。一块拼片的三个格子必须使用同一字母。不同的、不相邻的拼片可以使用相同字母。

不要在行尾输出多余空格。 所有非点号格子必须能够构成满足上述条件的 V 形拼片,且拼片总数必须达到最大值。答案不唯一,输出任意满足要求的最优方案即可。

样例

样例 1

2
 .
. .

样例 2

3
  W
 W .
. W .

样例 3

4
   .
  . R
 . B R
B B R .