翻纸牌游戏（dfs回溯）

翻纸牌游戏

Time Limit : 9000/3000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 2 Accepted Submission(s) : 2

Problem Description

有一种纸牌游戏，很有意思，给你N张纸牌，一字排开，纸牌有正反两面，开始的纸牌可能是一种乱的状态（有些朝正，有些朝反），现在你需要整理这些纸牌。但是麻烦的是，每当你翻一张纸牌（由正翻到反，或者有反翻到正）时，他左右两张纸牌（最左边和最右边的纸牌，只会影响附近一张）也必须跟着翻动，现在给你一个乱的状态，问你能否把他们整理好，使得每张纸牌都正面朝上，如果可以，最少需要多少次操作。

Input

有多个case，每个case输入一行01符号串（长度不超过20），1表示反面朝上，0表示正面朝上。

Output

对于每组case，如果可以翻，输出最少需要翻动的次数，否则输出NO。

Sample Input

01 011 

Sample Output

NO 1 

题解：find函数应该放到最前，错了半天。。。

代码1;

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define MIN(x,y)(x<y?x:y)
 4 int len,flot,ans;
 5 int s[25];
 6 void turn(int x){
 7     s[x]=!s[x];
 8     if(x-1>=0)s[x-1]=!s[x-1];
 9     if(x+1<len)s[x+1]=!s[x+1];
10 }
11 bool find(){
12     for(int i=0;i<len;i++){
13     //    printf("%d ",s[i]);
14         //if(s[i])puts("");
15         if(s[i])return false;
16     }
17     return true;
18 }
19 void dfs(int x,int time){
20     if(find()){
21         flot=1;
22         ans=MIN(ans,time);
23         return;
24     }
25     if(x>=len)return;
26     dfs(x+1,time);
27     turn(x);
28     dfs(x+1,time+1);
29     turn(x);
30 }
31 int main(){
32     char m[20];
33     while(~scanf("%s",m)){
34         len=strlen(m);
35         for(int i=0;i<len;i++)s[i]=m[i]-'0';
36         s[len]='';
37         ans=0x3f3f3f3f;
38         flot=0;
39         dfs(0,0);
40         //printf("%d
",ans);
41         if(flot)printf("%d
",ans);
42         else puts("NO");
43     }
44     return 0;
45 }

代码2;

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define MIN(x,y)(x<y?x:y)
 4 int len,flot,ans;
 5 int s[25],cnt[25];
 6 void turn(int x){
 7     s[x]=!s[x];
 8     if(x-1>=0)s[x-1]=!s[x-1];
 9     if(x+1<len)s[x+1]=!s[x+1];
10 }
11 bool find(){
12     for(int i=0;i<len;i++){
13     //    printf("%d ",s[i]);
14         //if(s[i])puts("");
15         if(s[i])return false;
16     }
17     return true;
18 }
19 void dfs(int x){
20     if(find()){
21         flot=1;
22         int temp=0;
23         for(int i=0;i<len;i++)if(cnt[i]==1)temp++;
24         ans=MIN(ans,temp);
25         return;
26     }
27     if(x>=len)return;
28     for(cnt[x]=0;cnt[x]<2;){
29     turn(x);
30     cnt[x]++;
31     dfs(x+1);
32     }
33 }
34 int main(){
35     char m[20];
36     while(~scanf("%s",m)){
37         len=strlen(m);
38         for(int i=0;i<len;i++)s[i]=m[i]-'0';
39         s[len]='';
40         ans=0x3f3f3f3f;
41         flot=0;
42         memset(cnt,0,sizeof(cnt));
43         dfs(0);
44         //printf("%d
",ans);
45         if(flot)printf("%d
",ans);
46         else puts("NO");
47     }
48     return 0;
49 }