$$\color{Purple}{kuangbin题解目录}$$
描述
给定一个 $M \\times N$ 的 $01$ 矩阵。
你需要选择其中一些元素,并对选择的元素进行翻转操作。
翻转操作是指将所选元素以及与其上下左右相邻的元素(如果有)进行翻转($0$ 变 $1$,$1$ 变 $0$)。
我们希望最终矩阵变为一个全 $0$ 矩阵,并且选择进行翻转操作的元素数量尽可能少。
输出最佳翻转方案。
输入格式
第一行包含整数 $M,N$。
接下来 $M$ 行,每行包含 $N$ 个整数,每个整数为 $0$ 或 $1$。
输出格式
共 $M$ 行,每行包含 $N$ 个整数,其中第 $i$ 行第 $j$ 列的整数,表示第 $i$ 行第 $j$ 列元素的翻转次数。
如果翻转操作次数最少的操作方案不唯一,则输出字典序最小的方案。
如果不存在合理方案,则输出 IMPOSSIBLE
。
数据范围
$1 \\le M,N \\le 15$
输入样例:
4 4
1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1
输出样例:
0 0 0 0
1 0 0 1
1 0 0 1
0 0 0 0
思路
思想同费解的开关 费解的开关代码
先枚举第一行的所有状态(用二进制表示),然后逐层将当前位置$(x,y)$为$1$的将$(x+1,y)$进行翻转(避免后效性),最后判断最后一行是否均为0,满足条件更新最小翻转次数及翻转情况.
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#define MAXN 20
using namespace std;
const int inf=0x3f3f3f3f;
int m,n,cnt,res=inf;
int a[MAXN][MAXN],vis[MAXN][MAXN];
int temp[MAXN][MAXN];//暂存原数组并对它进行修改
int dir[5][2]={{0,0},{-1,0},{0,1},{1,0},{0,-1}};
int b[MAXN][MAXN];
void dfs(int x,int y)
{
for(int i=0;i<=4;i++)
{
int dx=x+dir[i][0],dy=y+dir[i][1];
if(dx>=0&&dx<=m-1&&dy>=0&&dy<=n-1)
temp[dx][dy]^=1;
}
vis[x][y]=1;
}
int main()
{
scanf("%d %d",&m,&n);
for(int i=0;i<=m-1;i++)
for(int j=0;j<=n-1;j++)
scanf("%d",&a[i][j]);
for(int state=0;state<(1<<n);state++)
{
cnt=0;
memset(vis,0,sizeof(vis));
memcpy(temp,a,sizeof(temp));
for(int i=0;i<=n-1;i++)//将该状态进行翻转
if((state>>i) &1)
dfs(0,i),cnt++;
for(int i=0;i<=m-2;i++)
for(int j=0;j<=n-1;j++)
if(temp[i][j]==1)
dfs(i+1,j),cnt++;
int flag=1;
for(int i=0;i<=n-1;i++)
if(temp[m-1][i]==1)
{
flag=0;
break;
}
if(cnt<res&&flag==1)
{
res=cnt;
memcpy(b,vis,sizeof(b));
}
}
if(res==inf)
printf("IMPOSSIBLE\n");
else
{
for(int i=0;i<=m-1;i++)
{
for(int j=0;j<=n-1;j++)
printf("%d ",b[i][j]);
printf("\n");
}
}
return 0;
}