Time Limit:?1 SecMemory Limit:?128 MB
Submit:?137Solved:?41
Description
有一種紙牌游戲，很有意思啃憎，給你N張紙牌颂跨，一字排開，紙牌有正反兩面犬缨，開始的紙牌可能是一種亂的狀態(tài)（有些朝正喳魏，有些朝反），現在你需要整理這些紙牌怀薛。但是麻煩的是刺彩，每當你翻一張紙牌（由正翻到反，或者有反翻到正）時枝恋，他左右兩張紙牌（最左邊和最右邊的紙牌创倔，只會影響附近一張）也必須跟著翻動，現在給你一個亂的狀態(tài)焚碌，問你能否把他們整理好畦攘，使得每張紙牌都正面朝上，如果可以十电，最少需要多少次操作知押。
Input
有多個case，每個case輸入一行01符號串（長度不超過1000）鹃骂，1表示反面朝上台盯，0表示正面朝上。
Output
對于每組case畏线，如果可以翻爷恳，輸出最少需要翻動的次數，否則輸出NO象踊。
Sample Input
01
011
1111
Sample Output
NO
1
2
HINT
對于第一組測試數據温亲，無論怎樣操作，都無法完成.
對于第二組測試數據杯矩，只需反轉一次最右面的牌即可
對于第三組測試數據栈虚，需要翻轉第一張牌和最后一張牌
***請使用scanf("%s",s)輸入，使用gets()可能會遇到麻煩
TE代碼史隆，沒有心思查了魂务。。。
#include <bits/stdc++.h>
#define Min(x,y)(x<y?x:y)
using namespace std;
int len,flot,ans;
int a[25],cnt[25];
void turn(int x){
a[x]=!a[x];
if(x-1>=0) a[x-1]=!a[x-1];
if(x+1<len)a[x+1]=!a[x+1];
}
bool find(){
for(int i=0;i<len;i++)
if(a[i]) return false;
return true;
}
void dfs(int x){
if(find()){
flot=1;
int temp=0;
for(int i=0;i<len;i++)
if(cnt[i]==1)
temp++;
ans=Min(ans,temp);
return;
}
if(x>=len)return;
for(cnt[x]=0;cnt[x]<2;){
turn(x);
cnt[x]++;
dfs(x+1);
}
}
int main()
{
int m, n;
char t[20];
while (~scanf("%s",t)){
len=strlen(t);
for(int i=0;i<len;i++)
a[i]=t[i]-'0';
ans=0x3f3f3f3f;//
flot=0;
memset(cnt,0,sizeof(cnt));
dfs(0);//深度優(yōu)先搜索
if(flot)printf("%d\n",ans);
else printf("NO\n");
}
return 0;
}
