【题解】51nod 1316 回文矩阵

题目传送门
题目描述
一个 $N\times M$ 的矩阵 $A$ 完全由 $0$ 与 $1$ 两个数字组成（$0<N,M\le 8$），矩阵第 $i$ 行第 $j$ 列上的项为 $A_{i,j}$，$i$ 与 $j$ 从 $0$ 标起，即 $0\le i<N$，$0<=j<M$。现在存在两种操作：
（1）将矩阵中的任一项 $A_{i,j}$ 改为数字 $1$；
（2）将矩阵中的任一项 $A_{i,j}$ 改为数字 $0$；
现在给出初始的矩阵 $A$，要求经过最少次操作，使矩阵 $A$ 中至少有 $RowCount$ 行是回文的，同时存在至少 $ColumCount$ 列是回文的。输出这个最少操作的次数。
矩阵中第r行是回文的，指序列 $A_{r,0},A_{r,1},???,A_{r,M?1}$回文，即所有的 $i$ 有 $A_{r,i}=A_{r,M?1?i}$；
矩阵中第c列是回文的，指序列 $A_{0,c},A_{1,c},...A_{N?1,c}$ 回文，即所有的 $i$ 有 $A_{i,c}=A_{N?1?i,c}$。

例如 $4\times 4$ 的矩阵如下：

0000
1000
1100
1110

要求 $RowCount=2$，且 $ColumCount=2$。
可以将 $A_{3,0}$ 改为 $0$，使第 $0$ 行与第 $3$ 行回文，同时第 $0$ 列与第 $3$ 列回文。变化后如下：

0000
1000
1100
0110

输入格式
第一行两个正整数，表示 $RowCount$，$ColumCount$，且 $0\le RowCount\le N$，$0\le ColumCount\le M$。
第二行一个整数 $N$，即矩阵的行数，$1\le N\le 8$.
之后有 $N$ 行，每行一个由 $M$ 个 $\text{0}$、$\text{1}$ 字符构成的字符串，表示 $N\times M$ 矩阵的信息。

输出格式
一个整数，表示最少操作的次数。

输入样例

2 2
4
0000
1000
1100
1110

输出样例

1

对于这道题，毕竟 $N,M$ 只有 $8$，所以我们可以采取

暴力！

首先从 $N$ 行中枚举 $RowCount$ 行出来，从 $M$ 行中枚举 $ColomCount$ 行出来。这一点可以用深搜解决。然后计算一下把这些行列变成回文的最小步数。
在计算行的时候，考虑到后效性，枚举一个点，如果这一个点所在的列也被选中了，那么就要把这个点在这个列的对应点也考虑进去。如果这一个点在它所在的行的对应点所在的列也被选中了，那么就要把它的在它那一列的对应点也考虑进去。
拗口不？
结合图可以更好理解。

一个 $4\times 8$ 的矩阵，其中
红色点：枚举时选择的点；
绿色点：这个点在这个列的对应点；
黄色点：这个点在这个行的对应点；
蓝色点：这个点在这个行的对应点在其所在列的对应点；
箭头所指为选中的行和列。
将四个点中 $1$ 的数量以及 $0$ 的数量统计出来，少数服从多数。可以保证无后效性。
列同。
代码如下。

#include<bits/stdc++.h>
using namespace std;
int rc,cc,n,m,ans=0x7fffffff;
char s[10][10],s2[10][10];//s为原矩阵，s2是要修改的矩阵
int r[10],c[10];//选中的行和列
bool ru[10],cu[10];//行和列是否选中
void count()
{
    int tot=0;memcpy(s2,s,sizeof(s2));for(int i=1;i<=rc;i++)for(int j=1;j<=m/2;j++)//计算选中的行if(s2[r[i]][j]!=s2[r[i]][m-j+1])//字符不同{
    int a=1,b=1;//a为0的数量，b为1的数量if(cu[j])//所在列被选中{
    if(s2[n-r[i]+1][j]=='0') a++;//判断所在列的对应点else b++;}if(cu[m-j+1])//对应点所在列被选中{
    if(s2[n-r[i]+1][m-j+1]=='0') a++;//计算对应点所在列的对应点else b++;}if(a>b)//0多，全部改成0{
    s2[r[i]][j]='0';s2[r[i]][m-j+1]='0';if(cu[j]) s2[n-r[i]+1][j]='0';if(cu[m-j+1]) s2[n-r[i]+1][m-j+1]='0';tot+=b;//累计修改数量}else//同上{
    s2[r[i]][j]='1';s2[r[i]][m-j+1]='1';if(cu[j]) s2[n-r[i]+1][j]='1';if(cu[m-j+1]) s2[n-r[i]+1][m-j+1]='1';tot+=a;}}for(int j=1;j<=cc;j++)//同上for(int i=1;i<=n/2;i++)if(s2[i][c[j]]!=s2[n-i+1][c[j]]){
    int a=1,b=1;if(ru[i]){
    if(s2[i][m-c[j]+1]=='0') a++;else b++;}if(ru[n-i+1]){
    if(s2[n-i+1][m-c[j]+1]=='0') a++;else b++;}if(a>b){
    s2[i][c[j]]='0';s2[n-i+1][c[j]]='0';if(ru[i]) s2[i][m-c[j]+1]='0';if(ru[n-i+1]) s2[n-i+1][m-c[j]+1]='0';tot+=b;}else{
    s2[i][c[j]]='1';s2[n-i+1][c[j]]='1';if(ru[i]) s2[i][m-c[j]+1]='1';if(ru[n-i+1]) s2[n-i+1][m-c[j]+1]='1';tot+=a;}}ans=min(ans,tot);
}
void col(int k)//dfs枚举列
{
    if(k==cc+1) count();else for(int i=c[k-1]+1;i<=m;i++){
    c[k]=i;cu[i]=true;col(k+1);cu[i]=false;}
}
void row(int k)//dfs枚举行
{
    if(k==rc+1) col(1);else for(int i=r[k-1]+1;i<=n;i++){
    r[k]=i;ru[i]=true;row(k+1);ru[i]=false;}
}
int main()
{
    scanf("%d%d%d%s",&rc,&cc,&n,s[1]+1);m=strlen(s[1]+1);for(int i=2;i<=n;i++) scanf("%s",s[i]+1);row(1);printf("%d",ans);return 0;
}