> 给一个N行M列的矩阵,值分别为0和1,每次你可以选择将一个变成相反状态,同时,它周围的四个数也会变为相反状态。
问:最少翻转多少次,可以将所有值都变成0
多个解,输出翻转次数最少的(若有次数相同解,输出字典序小的)
若无解,输出”IMPOSSIBLE”
显然一个数字只能翻转一次,那就按照字典序枚举第一行的所有可能,记录下答案最小的一个。然后每一个数看它上面是否为0,如果是就不管,如果不是就要反转当前的数字。
实现细节还是要注意的,感觉统计当前状态的思路也不错。
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#define inf 0x3f3f3f3f
int dx[5]={0,0,-1,0};
int dy[5]={1,-1,0,0};
int a[25][25];
int f[25][25];
int ans[25][25];
int best=inf; int m,n;
inline int Judge(int x,int y){
int tmp=a[x][y];
for(int i=0;i<=3;++i){
int gx=x+dx[i];
int gy=y+dy[i];
if(gx<1||gy<1||gx>m||gy>n) continue;
tmp+=f[gx][gy];
}
return tmp&1;
}
int main (){
// freopen("data.txt","r",stdin);
// freopen("my.out","w",stdout);
while(scanf("%d %d",&m,&n)!=EOF){
best=inf;
for(int i=1;i<=m;++i)
for(int j=1;j<=n;++j)
scanf("%d",&a[i][j]);
for(int i=0;i<=(1<<n)-1;++i){
memset(f,0,sizeof(f));
for(int j=1;j<=n;++j){
f[1][n-j+1]=(i>>(j-1))&1;
}
for(int k=2;k<=m;++k){
for(int j=1;j<=n;++j){
if(Judge(k-1,j))
f[k][j]=1;
}
}
int flag=1;
for(int k=1;k<=n;++k){
if(Judge(m,k)){
flag=0;
break;
}
}
if(flag==1){
int tmp=0;
for(int k=1;k<=m;++k){
for(int j=1;j<=n;++j){
tmp+=f[k][j];
}
}
if(tmp<best){
best=tmp;
for(int k=1;k<=m;++k){
for(int j=1;j<=n;++j){
ans[k][j]=f[k][j];
}
}
}
}
}
if(best==inf){
printf("IMPOSSIBLE");
}
else{
for(int i=1;i<=m;++i){
for(int j=1;j<=n;++j){
if(j==n)
printf("%d\n",ans[i][j]);
else
printf("%d ",ans[i][j]);
}
}
}
}
return 0;
}
```
0 条评论