题目

来源

中国MOOC网，程序设计与算法（二）第一周作业1 http://cxsjsxmooc.openjudge.cn/2017t2sPRinghw1/1/

限制

总时间限制: 1000ms 内存限制: 1024kB

描述

有一种特殊的二进制密码锁，由n个相连的按钮组成（n<30），按钮有凹/凸两种状态，用手按按钮会改变其状态。

然而让人头疼的是，当你按一个按钮时，跟它相邻的两个按钮状态也会反转。当然，如果你按的是最左或者最右边的按钮，该按钮只会影响到跟它相邻的一个按钮。

当前密码锁状态已知，需要解决的问题是，你至少需要按多少次按钮，才能将密码锁转变为所期望的目标状态。

输入

两行，给出两个由0、1组成的等长字符串，表示当前/目标密码锁状态，其中0代表凹，1代表凸。

输出

至少需要进行的按按钮操作次数，如果无法实现转变，则输出impossible。

样例输入

011 000

样例输出

1

解题报告

思路分析

首先思考枚举法，每个按钮有2种状态，但是最多可能有30个灯，因此状态有2^30之多，穷举一定会超时。

重点1 一个灯如果按了第二下，就会抵消上一次按下所产生的影响。因此，一个灯只有按或者不按两种情况，不存在一个灯要开关多次的情况。

例如八个灯 00000000 按1后 11000000 按3后 10110000 按1后 01110000 这和八个灯 00000000 只按一次3后 01110000 是完全相同的情况

重点2 我们只需要考虑是否按下第一个灯。因为如果第一个灯的状态被确定了，那么是否按下第二个灯也就决定了（如果第一个灯与期望不同，则按下，如果期望相同，则不按下）同理，第三个灯是否按下也唯一确定。

所以，本题只要分两种情况：灯1被按下和没有被按下 之后使用for循环判断别的灯是否需要按下即可 

当循环结束，若现在的灯况与答案相同，则输出两种方案中按键次数最少的，若不同，则impossible！

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;// 枚举第一个按钮是否按下的两种情况即可，对于指定的一种情况，后面的事情都是确定的int oriLock;int lock;int destLock;inline void SetBit(int& n, int i, int v){	if (v)   // v 为1 	{		n |= (1 << i);   // 设置 n 的第 i 位为 1;	}	else		n &= ~(1 << i);  // 设置 n 的第 i 位为0;}inline void  FlipBit(int &n, int i){	n ^= (1 << i);  // 与 1 异或跳转，与 0 异或保持不变}inline int GetBit(int n, int i){	return (n >> i) &	1;  // 返回 n 的 第 i 位}int main(){	char line[40];	destLock = lock = oriLock = 0;	cin >> line;	int N = strlen(line);	for (int i = 0; i < N; ++i)		SetBit(oriLock, i, line[i] - '0'); // oriLock 保存原字符数组的每一位	cin >> line;	for (int i = 0; i < N; ++i)		SetBit(destLock, i, line[i] - '0');	int minTimes = 1 << 30;	for (int p = 0; p < 2; ++p)	{ // p 代表最左边按钮, p 可能为0，或1		lock = oriLock;     		int times = 0;    // 统计次数		int curButton = p;		for (int i = 0; i < N; ++i)		{			if (curButton)			{				++times;				if (i > 0)					FlipBit(lock, i - 1);				FlipBit(lock, i);				if (i < N - 1)					FlipBit(lock, i + 1);			}			if (GetBit(lock, i) != GetBit(destLock, i))				curButton = 1;			else				curButton = 0;		}		if (lock == destLock)			minTimes = min(minTimes, times);		if (minTimes == 1 << 30)			cout << " impossible" << endl;		else			cout << minTimes << endl;	}	return 0;}