AcWing寒假每日一题——Day10翻硬币

1208翻硬币

一、问题描述

小明正在玩一个“翻硬币”的游戏。桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。比如，可能情形是： ∗ ∗ o o ∗ ∗ ∗ o o o o **oo***oooo ∗∗oo∗∗∗oooo。如果同时翻转左边的两个硬币，则变为： o o o o ∗ ∗ ∗ o o o o oooo***oooo oooo∗∗∗oooo。现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？我们约定：把翻动相邻的两个硬币叫做一步操作。
输入格式
两行等长的字符串，分别表示初始状态和要达到的目标状态。
输出格式
一个整数，表示最小操作步数
数据范围
输入字符串的长度均不超过100。数据保证答案一定有解。
输入样例：

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

输出样例：

5

二、问题分析

  本题可以这么想，每一个位置的硬币与目标状态是否一样只与它后面的硬币翻动有关，因为每次是相邻的两个硬币一起翻动，可将需要翻动的硬币与后面的硬币看作一组。且每个位置只会操作一次，如果两次等于无意义操作。假如第一个位置与目标状态不一致，我们将第一个和第二个位置硬币反转，然后再判断第二个位置与目标位置是否一致，若不一致，再将第二个位置与第三个位置硬币反转，以此类推…
代码如下（示例）：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
char q[1050], p[1050];
int sum;
int main()
{
	cin >> q >> p;
	for (int i = 0;i < strlen(q);i++)
	{
		if (q[i] != p[i])
		{
			if (q[i] == '*')q[i] = 'o';
			else q[i] = '*';
			if (q[i+1] == '*')q[i+1] = 'o';
			else q[i+1] = '*';
			sum++;
		}
	}
	cout << sum << endl;
	return 0;
}