https://codeforces.ml/contest/1327/problem/C
题意:给了个n*m的网格,k个已知点,和k个要到的点,每次可以选择方向让所有点一起动,每个点可以到的次数不限制,最多走不超过2mn步,现在求一种走法让所有要到的点至少做过一次
思路:第一眼是想要bfs的,然后公共说是不必要求步数最少 那就是个构造题了
我们先考虑极端,就是把一个已知点当成在(1,1)这个位置,那么我们先直接往下一直走,然后往右一直走,然后在一步步倒着走回起点即可
#include<bits/stdc++.h>using namespace std;typedef long long ll;#define me(a,x) memset(a,x,sizeof a)#define rep(i,x,n) for(int i=x;i<n;i++)#define repd(i,x,n) for(int i=x;i<=n;i++)#define all(x) (x).begin(), (x).end()#define pb(a) push_back(a)#define paii pair<int,int>#define pali pair<ll,int>#define pail pair<int,ll>#define pall pair<ll,ll>#define x first#define y secondchar c[100005];int main(){int n,m,k;cin>>n>>m>>k;int cnt=0;for(int i=0;i<n;i++) c[cnt++]='D';for(int i=0;i<m;i++) c[cnt++]='R';for(int i=0;i<n;i++){for(int j=0;j<m-1;j++){if(i&1) c[cnt++]='R';else c[cnt++]='L';}if(i!=n-1) c[cnt++]='U';}cout<<cnt<<endl;c[cnt]='\0';puts(c);return 0;}