P9840 [ICPC2021 Nanjing R] Oops, It's Yesterday Twice More
注意到最后袋鼠要集中到一个点上，显然先走到四个角落之一再移动到点 \((a,b)\) 是最优的，可以证明，步数一定不超过 \(3(n-1)\)。
因为不知道具体要到哪一个角落里，因此记录 \((a,b)\) 到每个角落的距离并大力分类讨论即可。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, a, b;
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> a >> b;
int w, x, y, z;
w = a + b - 2, x = n * 2 - a - b + 2, z = n - b + 1 + a;
if (w <= n - 1) {
for (int i = 2; i <= n; i++) cout << 'U';
for (int i = 2; i <= n; i++) cout << 'L';
for (int i = 2; i <= a; i++) cout << 'D';
for (int i = 2; i <= b; i++) cout << 'R';
}
else {
if (x <= n - 1) {
for (int i = 2; i <= n; i++) cout << 'D';
for (int i = 2; i <= n; i++) cout << 'R';
for (int i = a + 1; i <= n; i++) cout << 'U';
for (int i = b + 1; i <= n; i++) cout << 'L';
}
else {
if (z <= n - 1) {
for (int i = 2; i <= n; i++) cout << 'U';
for (int i = 2; i <= n; i++) cout << 'R';
for (int i = 2; i <= a; i++) cout << 'D';
for (int i = b + 1; i <= n; i++) cout << 'L';
}
else {
for (int i = 2; i <= n; i++) cout << 'D';
for (int i = 2; i <= n; i++) cout << 'L';
for (int i = a + 1; i <= n; i++) cout << 'U';
for (int i = 2; i <= b; i++) cout << 'R';
}
}
}
return 0;
}