题解：AT_abc454_e [ABC454E] LRUD Moving

· · 题解

给你一个 N\times N 的方格。在第 A 行，第 B 列有一个障碍。问能否从第一行第一列走 N^2-2 步到第 N 行第 N 列。如果能，输出 Yes 并打印路径，如果不能，输出 No。注意，不能走重复的格子。

将第 i 行，第 j 列的格子表示为 (i,j)，如果 i+j 为偶数。那么我们将它称为偶数格子。如果 i+j 为奇数，我们将它称为奇数格子。

以一个偶数格子为起点，走奇数步，会到达一个奇数格子。
以一个偶数格子为起点，走偶数步，会到达一个偶数格子。

因为起点 (1,1) 和终点 (N,N) 都为偶数格子，所以中间的步数一定要为偶数才合法。所以，使 N^2-2 为偶数需要让 N 为偶数。

每个奇数格子的周围都是偶数格子，每个偶数格子的周围都是奇数格子。所以路径一定为：偶、奇、偶、……、偶。这里的偶数格子数量比奇数格子数量多 1。所以 A+B 一定要为奇数。否则到不了 (N,N)。

如果靠上下左右有完整的的两条。可以直接去掉，不影响中间重要的部分。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
//const int N = ;
int n,a,b,m,z;
void sto_orz(){
    cin >> n >> a >> b;
    m = n,z = n;
    if (n % 2 == 1 || (n%2==0 && (a+b)%2==0)){
        cout << "No\n";
        return;
    }
    int lh = 0,rh = 0;
    cout << "Yes\n";
    while (a > 2){
        a -= 2;
        n -= 2;
        lh ++;
    }
    while (a+2<=n){
        n-=2;
        rh ++;
    }
    int lw = 0,rw = 0;
    while (b > 2){
        b -= 2;
        m -= 2;
        lw++;
    }
    while (b+2<=m){
        m-=2;
        rw++;
    }
    for (int i = 1;i <= lh;i++){
        cout << string(z-1,'R');
        cout << "D";
        cout << string(z-1,'L');
        cout << "D";
    }
    for (int i = 1;i <= lw;i++){
        cout << "DRUR";
    }
    if (a == 2 && b == 1){
        cout << "RD";
    }else{
        cout << "DR";
    }
    for (int i = 1;i <= rw;i++){
        cout << "RURD";
    }
    for (int i = 1;i <= rh;i++){
        cout << "D";
        cout << string(z-1,'L');
        cout << "D";
        cout << string(z-1,'R');
    }
    cout << "\n";
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T; cin >> T;
    while (T--){
        sto_orz();
    }
    return 0;
}