本文主要是介绍B - Memory and Trident CodeForces - 712B(回到原点,水题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Input
The first and only line contains the string s (1 ≤ |s| ≤ 100 000) — the instructions Memory is given.
Output
If there is a string satisfying the conditions, output a single integer — the minimum number of edits required. In case it’s not possible to change the sequence in such a way that it will bring Memory to to the origin, output -1.
Examples
Input
RRU
Output
-1
Input
UDUR
Output
1
Input
RUUR
Output
2
Note
In the first sample test, Memory is told to walk right, then right, then up. It is easy to see that it is impossible to edit these instructions to form a valid walk.
In the second sample test, Memory is told to walk up, then down, then up, then right. One possible solution is to change s to “LDUR”. This string uses 1 edit, which is the minimum possible. It also ends at the origin.
题意: 模拟走的过程,问最少改变多少步能回到原点。
思路: y轴方向位移和x轴方向位移首先能够自抵,然后互抵。自抵也就是除以2,互抵也就是自抵剩下的比较。实现过程中因为思路不清晰还wa了两发,看来得先想清楚再实现。
#include<iostream>
#include<stdio.h>
#include<map>
#include<cstring>
#include<algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cstdlib>
#include <string>
using namespace std;const int maxn = 1e5 + 7;
char str[maxn];
int vis[4];
int main()
{scanf("%s",str);int len = strlen(str);for(int i = 0;i < len;i++){if(str[i] == 'R'){vis[0] ++;}else if(str[i] == 'L'){vis[1]++;}else if(str[i] == 'U'){vis[2]++;}else if(str[i] == 'D'){vis[3]++;}}int ans1 = abs(vis[0] - vis[1]);int ans2 = abs(vis[2] - vis[3]);int ans = 0;ans += ans1 / 2 + ans2 / 2;ans1 %= 2;ans2 %= 2;if(ans1 == ans2){ans += ans1;printf("%d\n",ans);}else{printf("-1\n");}return 0;
}
这篇关于B - Memory and Trident CodeForces - 712B(回到原点,水题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!