Game with Chips

Created by LXC on Fri Mar 8 11:27:08 2024

https://codeforces.com/problemset/problem/1327/C

ranting: 1600

tag: constructive algorithms, implementation

problem

Petya 有一个大小为 $n×m$ 的矩形版。一开始，在板子上有 $k$ 个芯片，第 $i$ 个芯片位置位于第 $sx$ 行与第 $sy$ 列的相交点上。

在一次操作中， Petya 可以把所有的芯片向左、向右、向下或者向上移动一格。

如果芯片在 $(x, y)$ 格中，则在操作之后：

• 往左：坐标为 $(x, y - 1)$;
• 往右：坐标为 $(x, y + 1)$;
• 往下：坐标为 $(x + 1, y)$;
• 往上：坐标为 $(x - 1, y)$;

如果现在芯片在版的边缘上，然而 Petya 将其移向边缘，那么芯片的位置保持不变。

对于每一个芯片， Petya 选择了他应该到达的位置。注意：芯片不须在这个地方停下来。

由于 Petya 时间不多， 总操作数不能超过 $2nm$。

你需要求出 Petya 应该做的操作：在不超过 $2nm$ 的操作里让每个芯片走过 Petya 选定的位置一遍。或者说明是不可能达到目的的。

第一行三个整数 $n,m,k$（$1 \le n,m,k \le 200$），分别表示矩形板的长，矩形板的宽和芯片的个数。

接下来的 $k$ 行每行两个整数 $ sx_i, sy_i$ （$1 \le sx_i \le n, 1 \le sy_i \le m$），表示第 $i$ 个芯片的初始位置。

再接下来的 $k$ 行每行两个整数 $ fx_i, fy_i$ （$1 \le fx_i \le n, 1 \le fy_i \le m$），表示第 $i$ 个芯片须达到的位置。

输出第一行一个整数，表示能达到目的的操作次数（不需要最小）。

在第二行输出一个序列，用 “L、R、D、U” 分别表示 “左、右、下、上” 。

若无解，则输出 $ -1 $ 。

solution

全部聚集到$(1,1)$花费n+m-2步。 从$(1,1)$开始遍历所有点花费$nm-1$步。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    int n, m, k;
    cin >> n >> m >> k;
    for (int i=0; i<2*k; i++) {
        int x, y;
        cin >> x >> y;
    }
    cout << (n+m-2)+n*(m-1)+(n-1) << "\n";
    cout << string(n-1, 'U')+string(m-1, 'L');
    for (int i=0; i<n; i++) {
        if(i) cout << "D";
        if (i%2) cout << string(m-1, 'L');
        else cout << string(m-1, 'R');
    }
    cout << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}