问题描述
给你三个正整数 N,A,BN,A,B，保证 AA 和 BB 都在 11 到 NN 之间（含端点）。
有一个 N×NN×N 的格子棋盘。棋盘中第 ii 行（从上往下数）第 jj 列（从左往右数）的格子记为 (i,j)(i,j)。起始时，棋子放在格子 (1,1)(1,1) 上。
你需要通过连续走 N2−2N2−2 步，每一步都只能向上下左右相邻的格子移动，把棋子从 (1,1)(1,1) 移动到 (N,N)(N,N)，并且要保证除了 (A,B)(A,B) 这个格子以外，所有格子都被访问过一次且仅一次（中途不能重复访问任何格子，包括起点 (1,1)(1,1) 和终点 (N,N)(N,N)）。
请判断是否存在这样一条路径，如果存在，请输出其中一条。
你需要处理 TT 组测试数据。
约束条件
- 1≤T≤50001≤T≤5000
- 2≤N≤1032≤N≤103
- 1≤A,B≤N1≤A,B≤N
- (A,B)≠(1,1),(N,N)(A,B)\=(1,1),(N,N)
- 所有测试数据中 N2N2 的总和不超过 106106。
- 所有输入均为整数。
输入格式
输入从标准输入读取，格式如下：
TT
case1case1
case2case2
⋮⋮
caseTcaseT
每组测试数据格式为：
NN AA BB
输出格式
请按顺序输出每组测试数据的答案，每组答案之间换行。
若不存在满足条件的路径，输出 No。
若存在，请按如下格式输出：
Yes
S1S2…SN2−2S1S2…SN2−2
其中 SkS**k 表示第 kk 步移动的方向，假设移动前棋子在 (i,j)(i,j)：
- Sk=S**k=
L表示棋子从 (i,j)(i,j) 移动到 (i,j−1)(i,j−1) - Sk=S**k=
R表示棋子从 (i,j)(i,j) 移动到 (i,j+1)(i,j+1) - Sk=S**k=
U表示棋子从 (i,j)(i,j) 移动到 (i−1,j)(i−1,j) - Sk=S**k=
D表示棋子从 (i,j)(i,j) 移动到 (i+1,j)(i+1,j)
如果有多条满足条件的路径，输出任意一条即可。
看第一个测试用例。
棋子从 (1,1)(1,1) 开始，按下面的步骤移动两步：
- 向下移动，棋子来到 (2,1)(2,1)。
- 向右移动，棋子来到 (2,2)(2,2)。
这条移动序列满足题目要求。
算法分析
运用黑白染色
如上图所示，我们要从黑->黑，如果n是奇数或a+b是偶数就一定无解，输出“No”。
输出路线包含以下两种：
1.当a<2并且b<2时，就可以直接按照蛇形的路线去输出，跳过禁点即可.
2.当a>2或b>2时，就两行（两列）的按蛇形输出路径，把这两行（两列）“删除“，直到a<2（b<2），再做第一步的操作即可。
AC代码：
#include <bits/stdc++.h>
using namespace std;
int T;
int n,a,b;
void solve(){if(n%2==1 || (a+b)%2==0){cout<<"No\n";return ;}bool flag;if(a%2==1){flag = true;}else{flag = false;}if(flag==false){swap(a,b);}#define lt j--,s+=flag?'L':'U'#define rt j++,s+=flag?'R':'D'#define up i--,s+=flag?'U':'L'#define dn i++,s+=flag?'D':'R'int i = 1;int j = 1;string s;for(; i<a; dn){if(i%2==1){for(; j<n; rt);}else{for(; j>1; lt);}}dn;rt;for(; j<b;){up;rt;dn;rt;}for(; j<n;){rt;up;rt;dn;}dn;for(; i<=n;){if(i%2==1){for(; j>1;){lt;}}else{for(; j<n;){rt;}}dn;}s.pop_back();cout<<"Yes\n"<<s<<endl;
}
int main(){cin>>T;while(T--){cin>>n>>a>>b;solve();}return 0;
}