2013蓝桥杯软件设计大赛 c/c++ B组第八题

2013蓝桥杯软件设计大赛 c/c++ B组第8题

题目：

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

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

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

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

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

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

程序输出：
一个整数，表示最小操作步数

例如：
用户输入：
**********
o****o****

程序应该输出：
5

再例如：
用户输入：
*o**o***o***
*o***o**o***

程序应该输出：
1

这是一个类似于隐式搜索类型的题目。

解题报告：

因为每个硬币能同时控制与其相邻的，那么我们这么设置，每个硬币只能控制该硬币的前一个硬币，这样意味着第一个硬币是不能被反转的。这样设置和题目是一样的意思。

关键点： 1、每个硬币只能被反转1次，因为如果反转的次数是偶数，那么就等于没有反转，是奇数，那就等于是反转了一次。

2、由上面的设定可知，第一个硬币是不能被反转的，那么当第一枚硬币和题目给出的目标不一样时，那么第二枚硬币肯定要被反转，以此类推，我们就能得到最少的反转次数。

代码：

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std; 
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

char xy[1010] , goal[1010];
int xy_1[1010] , goal_1[1010];
int length;

int main(int argc, char** argv) 
{
	while(scanf("%s" , xy) != EOF)
	{
		scanf("%s" , goal);
		length = strlen(xy);
		int i;
		for(i = 0; i < length; i++)
		{
			if(xy[i] == '*')  xy_1[i] = 1;
			else xy_1[i] = 0;
			if(goal[i] == '*')  goal_1[i] = 1;
			else goal_1[i] = 0;
		}
		int sum = 0;
		for(i = 1; i < length; i++)
		{
			if(xy_1[i-1] != goal_1[i-1])
			{
				sum += 1;
				goal_1[i] ^= 1;
			}
		}
		cout<<sum<<endl;
	}
	return 0;
}

2013蓝桥杯软件设计大赛 c/c++ B组第八题

相关推荐