【模拟+递归+位运算】POJ1753-Flip Game

由于数据规模不大，利用爆搜即可。第一次用位运算写的，但是转念一想应该用递归更加快，因为位运算没有剪枝啊(qДq )

【思路】

位运算：时间效率较低(172MS)，有些辜负了位运算的初衷。首先将二维数组倒序看作一个二进制数num。我们假设1代表翻转，0代表不翻转，可以发现以下规律：0 xor 1=1,1 xor 1=0;0 xor 0=0,1 xor 0=1，恰巧满足异或运算。我们假设另一个二进制数i∈[0,2^16)，通过异或运算就可以模拟出所有清形。

用check和i进行&操作可以求出以哪些位置为中心进行翻转。假设当前要翻转的方格在二进制数num中所在位数为k，则翻转它时同时翻转的四个方格（假设存在的话）分别为(k-1),(k+1),(k-4),(k+4),则turn[k]=在这几位为1，其余均为0的二进制数，我在草稿纸上手工计算之后直接设在数组中。这样的好处在于，用turn与now直接进行异或操作，即可求出翻转后的情形。

之后通过求i的二进制中1的个数即可。这步操作有一个较为简便的方法，通过草稿纸上模拟就可以领悟。

 1 {
 2     int count = 0;
 3 
 4     while(x)
 5     {
 6         x = x & ( x - 1 );
 7         count++; 
 8     }
 9     printf("count = %d/n", count);
10 }

上述方法非常实用，要牢记。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int INF=100000;
 6 int num,min;
 7 int check[16]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768};
 8 int turn[16]={18,37,74,132,289,594,1188,2120,4624,9504,19008,33920,8448,20992,41984,18432};
 9 
10 void init()
11 {
12     int k=1;
13     for (int i=0;i<4;i++)
14     {
15         for (int j=0;j<4;j++)
16         {
17             char c;
18             scanf("%c",&c);
19             if (c=='w') num+=k;
20             k*=2;
21         }
22         getchar();
23     }
24 }
25 
26 int mainprocess()
27 {
28     int min=INF;
29     for (int i=0;i<65535;i++)
30     {
31         int now=num^i;
32         for (int j=0;j<16;j++)
33             if (check[j]&i) 
34             {
35                 now=now^turn[j];
36             }
37         if (now==0 || now==65535)
38         {
39             int ans=0,x=i;
40             while (x)
41             {
42                 x=x & (x-1);
43                 ans++;
44             }
45             if (ans<min) min=ans;
46         }
47     }
48     if (min==INF) return -1;
49         else return min;
50 }
51 
52 int main()
53 {
54    init();
55    int output=mainprocess();
56    if (output==-1) cout<<"Impossible"; else cout<<output;
57    cout<<endl;
58    return 0;
59 }

此外还可以通过递归+剪枝来完成，效率较高（47ms），计算量较小。值得注意的是c++中如果将数组传入子程序，传入的其实是地址。所以必须在子程序中设置临时数组来保存当前状态，回溯时再还给原来的数组。注意，这个临时数组必须在子程序中，我第一次写的时候误将它写在了主程序中，那么临时数组就完全失去了它的意义。

剪枝：如果当前情况下需要翻转的次数已经小于最小值，则递归不需要再继续。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 using namespace std;
 5 const int INF=100000;
 6 int map[4][4];
 7 int dx[4]={0,0,1,-1};
 8 int dy[4]={1,-1,0,0};
 9 int ans;
10 
11 void recurrence(int step,int turn)
12 {
13     int tempmap[4][4];
14     if (turn>=ans) return;
15     if (step==16)
16     {
17         int sum=0;
18         for (int i=0;i<4;i++)
19             for (int j=0;j<4;j++) sum+=map[i][j];
20         if (sum==0 || sum==16) ans=turn;
21     }
22     else
23     {
24         for (int k1=0;k1<4;k1++) 
25             for (int k2=0;k2<4;k2++) tempmap[k1][k2]=map[k1][k2];
26             
27         for (int i=0;i<2;i++)
28         {
29             if (i==1)
30             {
31                 int x=step/4,y=step%4;
32                 map[x][y]=1-map[x][y];
33                 for (int d=0;d<4;d++)
34                     if (x+dx[d]>=0 && x+dx[d]<4 && y+dy[d]>=0 && y+dy[d]<4) map[x+dx[d]][y+dy[d]]=1-map[x+dx[d]][y+dy[d]];
35             }
36             recurrence(step+1,turn+i);
37             for (int k1=0;k1<4;k1++) 
38                 for (int k2=0;k2<4;k2++) map[k1][k2]=tempmap[k1][k2];
39         }
40     }
41 }
42 
43 int main()
44 {
45     ans=INF;
46     for (int i=0;i<4;i++)
47     {
48         char c;
49         for (int j=0;j<4;j++)
50         {
51             scanf("%c",&c);
52             if (c=='w') map[i][j]=1; else map[i][j]=0;
53         }
54         getchar();
55     }
56     recurrence(0,0);
57     if (ans!=INF) cout<<ans<<endl;else cout<<"Impossible"<<endl;
58 }

【模拟+递归+位运算】POJ1753-Flip Game

相关推荐