C. Game with Chips
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Petya has a rectangular Board of size n×m. Initially, k chips are placed on the board, i-th chip is located in the cell at the intersection of sxi-th row and syi-th column.
In one action, Petya can move all the chips to the left, right, down or up by 1 cell.
If the chip was in the (x,y) cell, then after the operation:
left, its coordinates will be (x,y−1);
right, its coordinates will be (x,y+1);
down, its coordinates will be (x+1,y);
up, its coordinates will be (x−1,y).
If the chip is located by the wall of the board, and the action chosen by Petya moves it towards the wall, then the chip remains in its current position.
Note that several chips can be located in the same cell.
For each chip, Petya chose the position which it should visit. Note that it’s not necessary for a chip to end up in this position.
Since Petya does not have a lot of free time, he is ready to do no more than 2nm actions.
You have to find out what actions Petya should do so that each chip visits the position that Petya selected for it at least once. Or determine that it is not possible to do this in 2nm actions.
Input
The first line contains three integers n,m,k (1≤n,m,k≤200) — the number of rows and columns of the board and the number of chips, respectively.
The next k lines contains two integers each sxi,syi (1≤sxi≤n,1≤syi≤m) — the starting position of the i-th chip.
The next k lines contains two integers each fxi,fyi (1≤fxi≤n,1≤fyi≤m) — the position that the i-chip should visit at least once.
Output
In the first line print the number of operations so that each chip visits the position that Petya selected for it at least once.
In the second line output the sequence of operations. To indicate operations left, right, down, and up, use the characters L,R,D,U respectively.
If the required sequence does not exist, print -1 in the single line.
Examples
inputCopy
3 3 2
1 2
2 1
3 3
3 2
outputCopy
3
DRD
inputCopy
5 4 3
3 4
3 1
3 3
5 3
1 3
1 4
outputCopy
9
DDLUUUURR
題意:
給你 k 個點，告訴你它們的起點和終點，讓你找一條路徑，使每個點至少經過終點一次，路徑長度不超過2nm
思路：我們可以選擇在最右上的點把它移動到（0，0）的位置，也就是左下角，如果它已經到了左下角，那么其他的點也肯定到達左下角，然后我們從（0，0）的位置開始走S型，遍歷全圖，所以這樣每個點都能到達自己需要到達的點，最壞情況也就是（x+y）+n*m<2*n*m//（x，y）是給出的點中最右上的那個點
Tip:當然我們每次也可以選取（1，m)這個點，也就是最右上的那個位子，這樣可以省略找給出的點中最右上的的那個點，這樣的長度是 （n+m）+n*m<2*n*m ，
#include<bits/stdc++.h> using namespace std; int main() { int n,m,k; cin>>n>>m>>k; for(int i=0;i<k;i++) { int x,y; cin>>x>>y; } for(int i=0;i<k;i++) { int x,y; cin>>x>>y; } string s; for(int i=n-1;i>=0;i--) s+='D'; for(int i=m-1;i>=0;i--) s+='L'; for(int i=0;i<m;i++) { if(i%2==0) { for(int i=0;i<n-1;i++) { s+='U'; } if(i<m-1) s+='R'; } else{ for(int i=0;i<n-1;i++) { s+='D'; } if(i<m-1) s+='R'; } } cout <<s.size()<<endl; cout<<s<<endl; }View Code
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/24570.html
標籤：其他
上一篇：你也看不起做外包的程式員？
下一篇：寫給大忙人看的計算機網路參考模型