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;
}