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;
}