翻纸牌游戏

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

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

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

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

Input

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

Output

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

Sample Input

01
011

Sample Output

NO
1

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define INF 1 << 30;
 4 int a[25],cnt[25];
 5 int len,temp,ans;
 6 int OK()
 7 {
 8     int i;
 9     for(i = 0;i < len;i ++)
10         if(a[i])
11             return 0;
12     return 1;
13 }
14 
15 void dfs(int index)
16 {
17     int i;
18     if(OK())
19     {
20         temp = 0;
21         for(i = 0;i < len;i ++)
22             if(cnt[i] == 1)
23                 temp++;
24         if(temp < ans)
25             ans = temp;
26         return ;
27     }
28     if(index >= len)
29         return ;
30     for(cnt[index] = 0;cnt[index] < 2; )
31     {
32         a[index] ^= 1;
33         if(index > 0)
34             a[index-1] ^= 1;
35         if(index < len-1)
36             a[index+1] ^= 1;
37         cnt[index]++;
38         dfs(index+1);
39     }
40 }
41 
42 int main()
43 {
44     int i;
45     char str[22];
46     while(~scanf("%s",str))
47     {
48         len = strlen(str);
49         for(i = 0;i < len;i ++)
50             a[i] = str[i]-'0';
51         ans = INF;
52         memset(cnt,0,sizeof(cnt));
53         dfs(0);
54         if(ans!= 1<<30)
55             printf("%d
",ans);
56         else
57             printf("NO
");
58     }
59     return 0;
60 }