<题目链接>
<转载于 >>> >
题目大意：
给定一个M*N矩阵，有些是黑色（1表示）否则白色（0表示），每翻转一个（i，j),会使得它和它周围4个格变为另一个颜色，要求翻转最少的点，使得变为全白色的矩阵，输出这个标记了翻转点的矩阵，如果有多个最优解，输出字典序最小的那个矩阵，若没有解，输出IMPOSSIBLE。
解题分析：
由于一个点翻转两次则返回原来的状态，所以最优解每个点最多翻转一次，但是2^(M*N)过大，所以2^N枚举第一行的所有翻转方式（逆字典序枚举），确定一种方式之后第二行也就随之确定了，因为如果第一行处理后没有翻回白色的点：（i，j)，必须在第二行（i+1,j)翻回，否则将无法返回。反之第二行其他的点都处理为不翻转，要不然上一行的点会翻回黑色而无法改变。第二行ok后同理解决第三行，以此类推。处理到最后一行如果不是全白就输出IMPOSSIBLE。否则更新结果。
即，用二进制枚举第一行的翻转情况，然后2~n-1行按照上一行的情况来翻转，最后再判断最后一行是否全部为0，如果为0，则记录下翻转次数，随时更新答案。
#include<cstdio> #include<cstring> int t[30][30], tem[30][30], m[30][30]; //这里用一个数组记录翻转次数，再配合原来的点数，就能判断反转后的点数，这里很巧妙 int M,N,dir[5][2] = { 0,0,1,0,0,1,-1,0,0,-1 }; int get(int x, int y)//获得x,y点的颜色 //它本身的点数，再加上周围四个点反转的次数，就能得到它的真实点数 { int c = t[x][y]; for (int i = 0; i < 5; i++) { int x1 = x + dir[i][0], y1 = y + dir[i][1]; c += tem[x1][y1]; } return c % 2; } int cal() //计算2行及之后的，有解返回翻点数，无解返回-1 { for (int i = 2; i <= M; i++) for (int j = 1; j <= N; j++) if (get(i - 1, j) == 1) tem[i][j] = 1; //得到前n-1行的翻转次数 for (int i = 1; i <= N; i++) if (get(M, i))return -1; //如果最后一行有一个点不为0，说明枚举的第一行不符合要求s int res = 0; for (int i = 1; i <= M; i++) for (int j = 1; j <= N; j++) res += tem[i][j]; return res; //记录下需要翻转的总次数 } int main() { int min = -1; //次数>0可以这样初始化 scanf("%d%d", &M, &N); for (int i = 1; i <= M; i++) for (int j = 1; j <= N; j++) scanf("%d", &t[i][j]); for (int i = 0; i < (1 << N); i++) //枚举第一行的所有情况 { memset(tem, 0, sizeof(tem)); //初始化翻转数组 for (int j = 1; j <= N; j++) tem[1][j] = (i >> (j - 1)) & 1; //根据二进制得到第一行的翻转情况,这个技巧一定要掌握 int num = cal(); if (num >= 0 && (min<0 || min>num)) //取情况成立并且总翻转次数最小的 { min = num; memcpy(m, tem, sizeof(tem)); //记录下最后的翻转矩阵 } } if (min == -1)printf("IMPOSSIBLE "); else { for (int i = 1; i <= M; i++) for (int j = 1; j <= N; j++) printf("%d%c", m[i][j], j == N ? ' ' : ' '); } return 0; }
2018-08-30