问题描述
在 \(N \times N\) 的网格中，需要找到一条从左上角 \((1,1)\) 到右下角 \((N,N)\) 的路径，满足以下条件：
- 必经点：除了一个给定的障碍点 \((A,B)\) 之外，必须访问网格中的每一个格子
- 唯一性：每个格子只能访问一次（哈密顿路径）
- 步数固定：总共移动 \(N^2 - 2\) 步
- 移动规则：只能上下左右移动（U: 上, D: 下, L: 左, R: 右）
输入：\(N, A, B\)
输出：如果存在这样的路径，输出 "Yes" 并输出操作序列；否则输出 "No"
算法思路
1. 存在性判定（奇偶性检查）
将 \(N \times N\) 的格子进行黑白染色，\((i,j)\) 的颜色由 \(i+j\) 的奇偶性决定：
结论：必须满足 \(N\) 为偶数且 \(A+B\) 为奇数，否则直接输出 "No"。
2. 构造合法方案
将原 \(N \times N\) 问题逐步缩小，直到变成一个最简的 \(2 \times 2\) 核心区域。
3. 完整构造代码
#include <bits/stdc++.h>
using namespace std;
void prn(char ch,int c) {for (int i=1;i<=c;i++) cout<<ch;
}
int main(){int T;cin>>T;while (T--) {int n,a,b;cin>>n>>a>>b;if (n%2==1 || (a+b)%2==0 ) {cout<<"No\n";continue;}cout<<"Yes\n";int m=0;while (m+2<a) {prn('R',n-1);cout<<'D';prn('L',n-1);cout<<'D';m+=2;}int k=0;while (k+2<b) {cout<<"DRUR";k+=2;}if (k+1==b) cout<<"RD";else cout<<"DR";k+=2;while (k<n) {cout<<"RURD";k+=2;}m+=2;while (m<n) {cout<<"D";prn('L',n-1);cout<<"D";prn('R',n-1);m+=2;}cout<<"\n";}return 0;
}