#P18910. [2026多校联测]上下左右
[2026多校联测]上下左右
上下左右
题目描述
给定一个 的网格,行、列编号均为 至 。
你从左上角 出发,每一步可以移动到八个方向之一的相邻格子。你需要恰好移动 步,最终到达右下角 ,并且每个格子恰好访问一次(包括起点)。
在所有合法路径中,请最大化正右方向的移动次数,并输出一条达到最大值的路径。右上、右下方向的移动不计入正右方向的移动次数。
各方向对应的字符如下:
| 字符 | 方向 | 行号变化 | 列号变化 |
|---|---|---|---|
Q |
左上 | ||
W |
上 | ||
E |
右上 | ||
A |
左 | ||
D |
右 | ||
Z |
左下 | ||
X |
下 | ||
C |
右下 |
输入格式
第一行包含一个整数 ,表示测试用例数。
接下来 行,每行包含一个整数 。
输出格式
对于每个测试用例,输出两行:
- 第一行输出正右方向移动次数的最大值;
- 第二行输出一个长度为 的字符串,表示一条达到最大值的合法路径。
本题使用特殊评测。若有多种合法最优路径,可以输出任意一种。
样例 1
输入
1
2
输出
2
DZD
数据范围与子任务
对于所有数据,,。
| 子任务 | 分值 | 每个测试用例的附加限制 |
|---|---|---|
| 1 | 10 | |
| 2 | 15 | |
| 3 | 20 | 或 为奇数 |
| 4 | 或 | |
| 5 | 35 | 无 |
各子任务独立计分,需通过该子任务的全部测试点才能获得相应分数。