HDOJ搜索专题之翻纸牌游戏

BFS题，数学模型如下：

对于一个01序列（长度小于20），定义翻转操作为：选定序列中的一位，将其取反，并将其左右相邻的位（如果存在）取反，现给定一个初始序列，求最少需操作多少次使得序列变成全0序列。

分析：序列状态可用一个32位整数表示，状态数目最多为2²⁰，所以搜索不会超时，翻转操作可用异或运算来表示。

需注意的是，写好后别忘了测试n=1的情况。

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <math.h>
 4 #include <queue>
 5 using namespace std;
 6 typedef struct node
 7 {
 8   int s,t;
 9 }node;
10 queue<node> S;
11 node cur,next;
12 int d[20];
13 char s[21];
14 char vis[1<<20];
15 void bfs()
16 {
17   int i,ans;
18   bool success=false;
19   while(!S.empty()) S.pop();
20   memset(vis,0,sizeof(vis));
21   cur.t=0;
22   vis[cur.s]=1;
23   S.push(cur);
24   while(!S.empty()&&!success)
25   {
26     cur=S.front(),S.pop();
27     if(cur.s==0)  success=true,ans=cur.t;
28     for(i=0;i<20&&!success;i++)
29     {
30       next=cur;
31       next.t++;
32       next.s^=d[i];
33       if(next.s==0) success=true,ans=next.t;
34       else if(!vis[next.s])
35       {
36         vis[next.s]=1;
37         S.push(next);
38       }
39     }
40   }
41   if(success) printf("%d\n",ans);
42   else  puts("NO");
43 }
44 int main()
45 {
46   int i,n;
47   while(gets(s))
48   {
49     n=strlen(s);
50     d[0]=3;
51     if(n>1)
52     {
53       d[n-1]=3<<(n-2);
54       if(n>2) d[1]=3;
55       else  d[1]=7;
56       for(i=2;i<n-1;i++) d[i]=d[i-1]<<1;
57     }
58     cur.s=0;
59     for(i=0;i<n;i++)
60     {
61       cur.s=(cur.s<<1)+s[i]-'0';
62     }
63     if(n==1&&cur.s==1)  puts("1");
64     else  bfs();
65   }
66   return 0;
67 }