首页 > 代码库 > codeforces 712B. Memory and Trident
codeforces 712B. Memory and Trident
题目链接：http://codeforces.com/problemset/problem/712/B
题目大意：
给出一个字符串（由‘U‘‘D‘‘L‘‘R‘）,分别是向上、向下、向左、向右一个单位，问修改若干字符，可以回到原点。回不到原点输出 -1，可以则输出最少修改的步数。
解题思路：
如果是奇数步，则不可以回到原点 直接输出-1；
否则：分别统计出向各个方向的步数，求出 abs(U-D)+abs(L-R) 回不到原点多余的步数。然后让 剩余的步数/2 修改一处可以保证两个状态OK.(例如：DRUR=>DRUL,修改了最后一个R为L,不仅保证了RL,而且取消了了本身对应的L,故修改一处即可)。
AC Code:
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 int main() 5 { 6 string s; 7 int a[4]; 8 while(cin>>s) 9 {10 memset(a,0,sizeof(a));11 for(int i=0; i<s.size(); i++)12 {13 if(s[i]==‘L‘)a[0]++;14 if(s[i]==‘R‘)a[1]++;15 if(s[i]==‘U‘)a[2]++;16 if(s[i]==‘D‘)a[3]++;17 }18 if(s.size()%2)19 printf("-1\n");20 else printf("%d\n",(abs(a[0]-a[1])+abs(a[2]-a[3]))/2);21 }22 return 0;23 }
codeforces 712B. Memory and Trident
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。