翻硬币（宽搜，规律）蓝桥杯省赛

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

小明正在玩一个“翻硬币”的游戏。

桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。

比如，可能情形是：**oo***oooo

如果同时翻转左边的两个硬币，则变为：oooo***oooo

现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？

我们约定：把翻动相邻的两个硬币叫做一步操作，那么要求：

输入格式

两行等长的字符串，分别表示初始状态和要达到的目标状态。每行的长度<1000

输出格式

一个整数，表示最小操作步数。

样例输入1

********** o****o****

样例输出1

5

样例输入2

*o**o***o*** *o***o**o***

样例输出2

1

用手去模拟一遍，发现其实要是翻转是最小次数，只需要从第一个不同的位置开始翻转，翻转到下一个不同的位置就成功了，就是反转区间[第一个不同位置，第二个不同位置],[第三个不同位置，第四个不同位置]....，区间外的相同位置不用管它，因为反转了也是多余的操作，多个这样的区间将每个区间的翻转次数加和就行了

翻转的过程不需要模拟，可以发现规律，一段区间的翻转次数=右端点-左端点

#include<cstdio> #include<iostream> using namespace std; string s1,s2; int ans=0; int main(){ cin>>s1>>s2; int len = s1.length(); int strat=-1; for(int i=0;i<len;i++){ if(s1[i]!=s2[i]){//找到不同的位置 if(strat==-1){//区间起始点 strat=i; //cout<<i<<endl; }else{//区间结束点 ans+=(i-strat);//加和反转次数 strat=-1;//恢复准备下一个区间的开始 } } } cout<<ans<<endl; return 0; }

还可以利用宽搜解决，但是注意要记录每个搜索出来的状态，防止多余搜索

#include<iostream> #include<cstdio> #include<queue> #include<set> using namespace std; string s1,s2; struct node{ string s; int step; node(string ss,int pp){ this->s=ss; this->step=pp; } }; queue<node> que; set<string> se;//记录出现过的状态 int main(){ cin>>s1>>s2; que.push(node(s1,0)); se.insert(s1); while(!que.empty()){ string str = que.front().s; if(str==s2){//变到了 cout<<que.front().step; return 0; } for(int i=0;i<s1.length()-1;++i){ string stro(str); if(stro[i]=='*')stro[i]='o'; else stro[i]='*'; if(stro[i+1]=='*')stro[i+1]='o'; else stro[i+1]='*'; if(!se.count(stro)){//只搜索没出现过的状态 que.push(node(stro,que.front().step+1)); se.insert(stro); } } que.pop(); } return 0; }