题目描述

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

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

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

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

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

我们约定：把翻动相邻的两个硬币叫做一步操作。

输入样例

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

输出样例

5

输入样例

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

输出样例

1

递推问题

当前数组与目标数组比较
对应位置如果不一样，就改变这个和下一个

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=110;
char g[N][N];

void turn(int i)
{
    if(g[0][i]=='*')g[0][i]='o';
    else if(g[0][i]=='o')g[0][i]='*';
}

int main ()
{

    for(int i=0;i<2;i++)
    {
        cin>>g[i];
    }

    int step=0;

    for(int i=0;i<100;i++)
    {
        if(g[0][i]!=g[1][i])
        {
            step++;
            turn(i);
            turn(i+1);
        }
    }
    cout<<step;
    return 0;
}