Fliptile POJ

除最后一行，其余各行的1都可以通过下一行的翻转成为0
也就是说除了最后一行，我们总可以通过翻转，将前n-1行变为0
翻转偶数次 = 未翻转，翻转奇数次 = 翻转1次故需要翻转则必为一次
因此我们可以得出：若该位置上一个位置为1则翻转，反之则不翻转
所以我们可以对第一行的翻转情况进行枚举，这里采用了二进制压缩的方法
将第一行看作一个n位的二进制数字找出1的所有位置即可
在找1位置时比如n = 4的情况我们可以让每一种情况与 1000 0100 0010 0001进行&运算

 1 #include <map>
 2 #include <set>
 3 #include <cmath>
 4 #include <queue>
 5 #include <string>
 6 #include <vector>
 7 #include <cstdio>
 8 #include <cstring>
 9 #include <iostream>
10 #include <algorithm>
11 #define forn(i, n) for (int i = 0; i < (n); i++)
12 #define forab(i, a, b) for (int i = (a); i <= (b); i++)
13 #define forba(i, b, a) for (int i = (b); i >= (a); i--)
14 #define mset(a, n) memset(a, n, sizeof(a))
15 #define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
16 #define P pair<int,int>
17 #define fi first
18 #define se second
19 using namespace std;
20 #define N 100005
21 #define maxn 1005
22 #define inf 0x3f3f3f3f
23 #define ll long long
24 int f[30][30];  //最终结果
25 int g[30][30];  //原矩阵
26 int t[30][30];  //临时答案
27 int cnt, n, m;
28 int xx[4] = {1, -1, 0, 0};
29 int yy[4] = {0, 0, 1, -1};
30 void flip(int i,int j)  //翻转
31 {
32     cnt++;
33     f[i][j] = 1;  //需要翻转则肯定只翻转一次
34     t[i][j] = !t[i][j];  //先将自己翻转
35     forab(k,0,3)
36     {
37         if(i+xx[k]>-1&&j+yy[k]>-1)
38         {
39             t[i + xx[k]][j + yy[k]] ^= 1;
40         }
41     }
42 }
43 bool judge(int k)
44 {
45     cnt = 0;   //步数清零
46     memcpy(t, g, sizeof(t));  //将初始情况复制到临时情况中
47     forab(j,0,m-1)    //枚举第一行
48     {
49         if (k & (1 << (m - 1 - j))) //如果第j位是1
50             flip(0, j);
51     }
52     forab(i, 1, n - 1)  //从第二行开始，如果某位置上面的位置为1则翻转
53         forab(j, 0, m - 1) 
54             if (t[i - 1][j]) 
55                 flip(i, j);
56     forab(j, 0, m - 1) //最后检查最后一行是否全为0
57         if (t[n - 1][j]) 
58             return false;
59     return true;
60 }
61 int main()
62 {
63     int ans;
64     int flag = -1;
65     scanf("%d%d", &n, &m);
66     forn(i, n)
67         forn(j, m)
68             scanf("%d", &g[i][j]);
69     ans = m * n + 1;
70     for (int i = 0; i < (1 << m);i++)
71     {
72         if(judge(i)&&cnt<ans)  //如果方法可行并且步数更优
73         {
74             ans = cnt;
75             flag = i;  //记录一下第一行的情况
76         }
77     }
78     mset(f, 0);  //初始化答案
79     if(flag>=0)
80     {
81         judge(flag);  //上面记录的最优情况
82         forn(i, n)
83             forn(j, m)
84                 printf("%d%c", f[i][j], j < m - 1 ? ' ' : '
');
85     }
86     else puts("IMPOSSIBLE");  //如果flag=-1证明所有情况都不可行
87 }

View Code