<题目链接>
<转载于 >>> >
题目大意：
给定一个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[][], tem[][], m[][];
//这里用一个数组记录翻转次数，再配合原来的点数，就能判断反转后的点数，这里很巧妙
int M,N,dir[][] = { ,,,,,,-,,,- }; int get(int x, int y)//获得x,y点的颜色 //它本身的点数，再加上周围四个点反转的次数，就能得到它的真实点数
{
int c = t[x][y];
for (int i = ; i < ; i++)
{
int x1 = x + dir[i][], y1 = y + dir[i][];
c += tem[x1][y1];
}
return c % ;
} int cal() //计算2行及之后的，有解返回翻点数，无解返回-1
{
for (int i = ; i <= M; i++)
for (int j = ; j <= N; j++)
if (get(i - , j) == )
tem[i][j] = ;
//得到前n-1行的翻转次数 for (int i = ; i <= N; i++)
if (get(M, i))return -; //如果最后一行有一个点不为0，说明枚举的第一行不符合要求s
int res = ;
for (int i = ; i <= M; i++)
for (int j = ; j <= N; j++)
res += tem[i][j];
return res; //记录下需要翻转的总次数
} int main()
{
int min = -; //次数>0可以这样初始化
scanf("%d%d", &M, &N);
for (int i = ; i <= M; i++)
for (int j = ; j <= N; j++)
scanf("%d", &t[i][j]);
for (int i = ; i < ( << N); i++) //枚举第一行的所有情况
{
memset(tem, , sizeof(tem)); //初始化翻转数组
for (int j = ; j <= N; j++)
tem[][j] = (i >> (j - )) & ; //根据二进制得到第一行的翻转情况,这个技巧一定要掌握 int num = cal();
if (num >= && (min< || min>num)) //取情况成立并且总翻转次数最小的
{
min = num;
memcpy(m, tem, sizeof(tem)); //记录下最后的翻转矩阵
}
} if (min == -)printf("IMPOSSIBLE\n");
else
{
for (int i = ; i <= M; i++)
for (int j = ; j <= N; j++)
printf("%d%c", m[i][j], j == N ? '\n' : ' ');
}
return ;
}
2018-08-30