[笔记] abc454_e LRUD Moving

E - LRUD Moving

看这题可能会联想到一笔画，但由于此题是“经过所有点各一次”，而非“经过所有边各一次”，所以不可使用欧拉路算法。

我们先考虑如何判断是否有解。

注意到，网格图是一个二分图，而二分图可以被黑白染色。所以，黑白染色就成了网格上分析的重要方法。

按 \(i+j\) 的奇偶性染色，奇数染成白色，偶数染成黑色。

注意到，经过的点（算上头和尾）一定是 \(1\rightarrow0\rightarrow1\rightarrow...\rightarrow1\) ，共经过 \(n^2-1\) 个点，且黑点比白点多一个。

此时，对 \(n\) 的奇偶性进行讨论。

1. \(n\) 为奇数

   \(n^2-1\) 为偶数，此时最后一个点一定为白色，而目标点 \((n,n)\) 应该为黑色，矛盾。所以 \(n\) 为奇数时无解。

2. \(n\) 为偶数

   设禁入点 \((A,B)\)

   • 如果 \(2\mid(A+B)\) ，则 \((A,B)\) 为黑点。可以发现，这种情况下，走到的白点比黑点多一个，与上面的结论矛盾。所以无解。
   • 如果 \(2 \nmid (A+B)\) ，走到的黑点比白点多一个，符合条件，有解。

---

判断有解性后，我们再考虑如何构造出解。

注意到，如果禁入点不再最上方两行，我们可以绕一个弯把最上面两行消掉，如图：

设 \((n,m,a,b)\) 表示在一个 \(n\times m\) 的方格图中，以 \(a,b\) 为禁入点的问题。

则经过上面的操作，原问题 \((n,m,a,b)\) 可转化为：先按 \(\text{RR...RDLL...LD}\) 的方式走，再解决子问题 \((n-2,m,a-2,b)\) 。类似的，后两行、前两列、后两列也可以这么干：

1. 如果禁入点不在后两行，则先解决子问题 \((n-2,m,a,b)\) ，再按 \(\text{DLL...LDRR...R}\) 走。
2. 如果禁入点不在前两列，则先按 \(\text{DD...DRUU...UR}\) 走 ，再解决子问题 \((n,m-2,a,b-2)\) 。
3. 如果禁入点不在后两列中，则先解决子问题 \((n,m-2,a,b)\) ，再按 \(\text{RUU...URDD...D}\) 走。

显然，四种情况必有一个满足，由此可用递归求解，边界条件即为 \(n=m=2\) 。

abc454_e

#include<bits/stdc++.h>
using namespace std;const int N=1e3+10;
string Ans;
int n,A,B;void solve(int a, int b, int c, int d){if(a==2 && b==2){if(c==1 && d==2) Ans+="DR";else Ans+="RD";return;}if(c>2){for(int i=1; i<b; i++) Ans+='R';Ans+='D';for(int i=1; i<b; i++) Ans+='L';Ans+='D';solve(a-2, b, c-2, d);}else if(a-c+1>2){solve(a-2, b, c, d);Ans+='D';for(int i=1; i<b; i++) Ans+='L';Ans+='D';for(int i=1; i<b; i++) Ans+='R';}else if(d>2){for(int i=1; i<a; i++) Ans+='D';Ans+='R';for(int i=1; i<a; i++) Ans+='U';Ans+='R';solve(a, b-2, c, d-2);}else{solve(a, b-2, c, d);Ans+='R';for(int i=1; i<a; i++) Ans+='U';Ans+='R';for(int i=1; i<a; i++) Ans+='D';}
}inline void SOLVE(){cin>>n>>A>>B;if((n&1) || !((A+B)&1)){cout<<"No\n"; return;}cout<<"Yes\n";Ans="";solve(n,n,A,B);cout<<Ans<<"\n";
}signed main(){cin.tie(0)->sync_with_stdio(0);int t; cin>>t;while(t--) SOLVE();return 0;
}