题目链接：http://poj.org/problem?id=3279
题意：给定一个n*m的坐标方格，每个位置为黑色或白色。现有如下翻转规则：每翻转一个位置的颜色，与其四连通的位置都会被翻转，但注意只扩散一圈，不是连锁反应。
求最少翻转几个位置能够使所有n*m个位置都变为白色。若有解，求字典序最小的翻转方案（给出每个位置的翻转次数）。
数据范围：n, m 属于 [1, 15]
思路：我们把翻转方案中的翻转称为“主动翻转”，翻转过程中受邻居影响而发生的翻转称为“被动翻转”。观察例子可得出如下几个结论：
1. 最优解中，每个位置的主动翻转不超过1次。
2. 各个位置翻转的次序对结果没有影响。
3. 某一时刻，位置(i, j)的颜色取决于到目前为止它的主动翻转和被动翻转次数之和，记为cnt；具体地，由结论1可推得cnt为奇数则变色，偶数则不变色。
4. 位置(i, j)的被动翻转次数 = 与它四连通的位置的主动翻转次数之和。
解法：首先枚举第一行的所有可能的翻转动作，这里由于m <= 15，所以用一个整型实现“状态压缩”，即枚举所有 i 属于[0, 2m-1]， i 的二进制展开的第 j 位代表原图第一行第 j 个位置是否主动翻转。
然后，由结论2、3，可对每个第一行的枚举值从第二行开始自上而下逐行递推：第 i-1 行通过第 i 行垂直位置的主动翻转而“修正”；具体地，对于位置（i, j），考查位置（i-1, j），若(i-1, j)为黑色，则目前一定要对(i, j)主动翻转才能带动(i-1, j)被动翻转为白色。这样的修正持续到最后一行，由于没有下一行可以修正最后一行，因此可直接判最后一行是否为全白，若不是则无解。
最后，对于最优解的维护，这里用二维数组b直接记录每个位置进行的主动翻转的次数。由结论3、4，可以通过数组b在O(1)时间内算出当前某个位置的颜色，以便判断是否需要修正。
解法和代码参照了http://blog.csdn.net/ac_hell/article/details/51077271 以及 http://blog.csdn.net/ac_hell/article/details/51077320，写得很清楚，学习了。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5 const int MAX_N = 16; 6 const int MAX_M = 16; 7 const int INF = 0x7fffffff; 8 int a[MAX_N][MAX_M];//原图 9 int b[MAX_N][MAX_M];//此位置共翻转了几次 10 int c[MAX_N][MAX_M];//最优解 11 int n, m; 12 int dx[] = {0, 0, 0, 1, -1}, dy[] = {1, -1, 0, 0, 0}; 13 14 bool out(int x, int y){ 15 if(x < 0 || x >=n || y < 0 || y >= m) return true; 16 return false; 17 } 18 19 int get_color(int x, int y){ 20 int color = a[x][y]; 21 for(int i=0; i<5; i++){ 22 int nx = x + dx[i], ny = y + dy[i]; 23 if(out(nx, ny)) continue; 24 color += b[nx][ny];//主动+被动 25 } 26 return color & 1; 27 } 28 29 int flip(int s){ 30 for(int i=1; i<=m; i++){ 31 b[0][i-1] = (s>>(m-i)) & 1; 32 //printf("%d ", b[0][i-1]); 33 } 34 for(int i=1; i<n; i++){ 35 for(int j=0; j<m; j++){//(i-1, j)想变，必须让(i, j)翻转 36 if(get_color(i-1, j)){ 37 b[i][j] = 1; 38 //printf("%d, %d\n", i, j); 39 } 40 } 41 } 42 for(int i=0; i<m; i++){ 43 if(get_color(n-1, i)){ 44 //printf("%d no\n", i); 45 return INF; 46 } 47 48 } 49 int times = 0; 50 for(int i=0; i<n; i++){ 51 for(int j=0; j<m; j++){ 52 times += b[i][j]; 53 } 54 } 55 return times; 56 } 57 58 int main() 59 { 60 freopen("3279.txt", "r", stdin); 61 scanf("%d%d", &n, &m); 62 for(int i=0; i<n; i++){ 63 for(int j=0; j<m; j++){ 64 scanf("%d", &a[i][j]); 65 } 66 } 67 int ans = INF; 68 for(int i=0; i< (1<<m); i++){//信号量集 69 memset(b, 0, sizeof(b));//翻转方案 70 int t = flip(i); 71 if(t < ans){ 72 ans = t; 73 memcpy(c, b, sizeof(b));//更新最优解 74 } 75 } 76 if(ans == INF) printf("IMPOSSIBLE\n"); 77 else{ 78 for(int i=0; i<n; i++){ 79 for(int j=0; j<m; j++){ 80 printf("%d ", c[i][j]); 81 } 82 printf("\n"); 83 } 84 } 85 return 0; 86 }
本来是做今天的计蒜之道的热身赛A题，与这道同类型。比赛时不会，然而比赛结束后已不能提交。。。