枚举：算法练习题目：特殊的密码锁

001:特殊密码锁

描述

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

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

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

输入

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

输出

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

样例输入

011
000

样例输出

1

这是第一次自己写的代码，简单的可以输出，复杂的测试用例

比如

011010110101010111111011111 000010111000000001101001110

会陷入死循环。这是第一次代码

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<math.h>

using namespace std;
int nows;
int targets;
int s;
int open_close;
inline int GetBit(int a,int i)
{
	return (a>>i)&1;
}
inline void SetBit(int &a,int i,int v)
{
	if(v)
	{
		a=a|(v<<i);
	}
	else
	{
		a=a&~(1<<i);
	}
}
inline void FlipBit(int &a,int i)
{
	a=a^(1<<i);
}

int main()
{
	char line[100];
	int m,sum=0;
	int min=100;
	scanf("%s",line);
	int n=strlen(line);
	for(int i=0;i<n;i++)
	{
		SetBit(nows,i,line[i]-0);
	}
	scanf("%s",line);
	n=strlen(line);
	for(int i=0;i<n;i++)
	{
		SetBit(targets,i,line[i]-0);
	}
	m=(int)pow(2.0,n);
	for(int p=0;p<=m-1;p++)
	{
		sum=0;
		open_close=p;
		s=nows;
		for(int i=0;i<n;i++)
		{
			if(GetBit(open_close,i))
			{
				sum++;
				FlipBit(s,i);
				if(i>0)
				{
					FlipBit(s,i-1);
				}
				if(i<n-1)
				{
					FlipBit(s,i+1);
				}
			}
		}
		if(targets==s)
		{
			if(min>sum)
			{
				min=sum;
			}
		}
	}
	if(min==100)
	{
		printf("impossible");
	}
	else
	{
	printf("%d",min);
	}
	return 0;
}

问题分析：应该是在进行二进制枚举的时候，2^n-1这个数太大了，如果n=27，则代码需要执行

一亿三千多万次，太死板，

解决方法：利用局部定，则其他的也定了的思想

只枚举最左面的开关，然后比如

用例：

011

000

当第二个1和目标状态不同时，按第三个按钮，可以保证不给前面的按钮添麻烦

可以说 前面的控制后面开关的是否按下，后面的开关决定前面的开关的状态

这是修改后的代码

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<math.h>

using namespace std;
int nows;
int targets;
int s;
int open_close;
inline int GetBit(int a,int i)
{
	return (a>>i)&1;
}
inline void SetBit(int &a,int i,int v)
{
	if(v)
	{
		a=a|(v<<i);
	}
	else
	{
		a=a&~(1<<i);
	}
}
inline void FlipBit(int &a,int i)
{
	a=a^(1<<i);
}

int main()
{
	char line[100];
	int m,sum=0;
	int min=100;
	scanf("%s",line);
	int n=strlen(line);
	for(int i=0;i<n;i++)
	{
		SetBit(nows,i,line[i]-0);
	}
	scanf("%s",line);
	n=strlen(line);
	for(int i=0;i<n;i++)
	{
		SetBit(targets,i,line[i]-0);
	}
	m=(int)pow(2.0,n);
	for(int p=0;p<2;p++)//p为最左面按钮
	{
		sum=0;
		open_close=p;
		s=nows;
		for(int i=0;i<n;i++)
		{
			if(open_close)
			{
				sum++;
				FlipBit(s,i);
				if(i>0)
				{
					FlipBit(s,i-1);
				}
				if(i<n-1)
				{
					FlipBit(s,i+1);
				}
			}
			if(GetBit(s,i)!=GetBit(targets,i))
			{
				open_close=1;
			}
			else
			{
				open_close=0;
			}
		}
		if(targets==s)
		{
			if(min>sum)
			{
				min=sum;
			}
		}
	}
	if(min==100)
	{
		printf("impossible");
	}
	else
	{
	printf("%d",min);
	}
	return 0;
}

新手上路，多多指教