时间限制: 1Sec 内存限制: 128MB 提交: 84 解决: 51
题目描述
小明正在玩一个“翻硬币”的游戏。
桌上放着排成一排的若干硬币。我们用 * 表示正面,用 o 表示反面(是小写字母,不是零)。
比如,可能情形是:**oo***oooo
如果同时翻转左边的两个硬币,则变为:oooo***oooo
现在小明的问题是:如果已知了初始状态和要达到的目标状态,每次只能同时翻转相邻的两个硬币,那么对特定的局面,最少要翻动多少次呢?
我们约定:把翻动相邻的两个硬币叫做一步操作。
桌上放着排成一排的若干硬币。我们用 * 表示正面,用 o 表示反面(是小写字母,不是零)。
比如,可能情形是:**oo***oooo
如果同时翻转左边的两个硬币,则变为:oooo***oooo
现在小明的问题是:如果已知了初始状态和要达到的目标状态,每次只能同时翻转相邻的两个硬币,那么对特定的局面,最少要翻动多少次呢?
我们约定:把翻动相邻的两个硬币叫做一步操作。
输入
两行等长的字符串,分别表示初始状态和要达到的目标状态。每行的长度< 1000
输出
一个整数,表示最小操作步数。
样例输入
*o**o***o*** *o***o**o***
样例输出
1
/* #include<cstdio> #include<cstring> #include<string> #include<queue> #include<set> #include<iostream> #include<algorithm> using namespace std; int ans = 0; string s1,s2; struct Node{ string s; int v; Node(string _s,int _v){ s=_s; v=_v; } }; queue<Node>q; set<string>se; int main(void) { cin>>s1>>s2; q.push(Node(s1,0)); se.insert(s1); while(!q.empty()) { Node temp=q.front(); q.pop(); string s = temp.s; int v=temp.v; if(s==s2) { ans = v; break; } for(int i=0;i+1<s.length();i++) { string ss=s; if(ss[i]!=s2[i]) { ss[i]=(ss[i]=='*'?'o':'*'); ss[i+1]=(ss[i+1]=='o'?'*':'o'); if(se.find(ss)==se.end()) { se.insert(ss); q.push(Node(ss,v+1)); } //q.push(Node(ss,v+1)); } } } printf("%d",ans); return 0; } */ #include<cstdio> #include<cstring> #include<iostream> using namespace std; int main(void) { string s1,s2; cin>>s1>>s2; int cnt=0; for(int i=0;i+1<s1.length();i++) { if(s1[i]!=s2[i]) { cnt++; s1[i]=(s1[i]=='*'?'o':'*'); s1[i+1]=(s1[i+1]=='*'?'o':'*'); } } printf("%d",cnt); return 0; }
就是类似使用贪心策略。不是很理解,就是使用STL类库超时了。