#P18910. [2026多校联测]上下左右

[2026多校联测]上下左右

上下左右

题目描述

给定一个 N×NN\times N 的网格,行、列编号均为 11 至 NN。

你从左上角 (1,1)(1,1) 出发,每一步可以移动到八个方向之一的相邻格子。你需要恰好移动 N2−1N^2-1 步,最终到达右下角 (N,N)(N,N),并且每个格子恰好访问一次(包括起点)。

在所有合法路径中,请最大化正右方向的移动次数,并输出一条达到最大值的路径。右上、右下方向的移动不计入正右方向的移动次数。

各方向对应的字符如下:

字符 方向 行号变化 列号变化
Q 左上 −1-1 −1-1
W 上 00
E 右上 11
A 左 00 −1-1
D 右 11
Z 左下 11 −1-1
X 下 00
C 右下 11

输入格式

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

接下来 TT 行,每行包含一个整数 NN。

输出格式

对于每个测试用例,输出两行:

  • 第一行输出正右方向移动次数的最大值;
  • 第二行输出一个长度为 N2−1N^2-1 的字符串,表示一条达到最大值的合法路径。

本题使用特殊评测。若有多种合法最优路径,可以输出任意一种。

样例 1

输入

1
2

输出

2
DZD

数据范围与子任务

对于所有数据,1≤T≤51\le T\le5,2≤N≤10002\le N\le1000。

子任务 分值 每个测试用例的附加限制
1 10 N≤3N\le3
2 15 N≤4N\le4
3 20 N≤4N\le4 或 NN 为奇数
4 N≤4N\le4 或 N≢0(mod4)N\not\equiv0\pmod4
5 35 无

各子任务独立计分,需通过该子任务的全部测试点才能获得相应分数。