5056. 【GDSOI2017模拟4.13】黑白广场

Description

东转盘有一个黑白广场，那是帕斯卡金最喜欢的地方。
传说中，这个一望无际的广场是个N行M列的网格图，每个格子都有黑白中的一种颜色。帕斯卡金有一根纤细的魔杖，他可以选择一个格子(i,j)，并且可以施加他仅有的两种魔法(任意次数，也可以不操作)：
1. 翻转(i,j)的颜色，以及翻转相邻格子的颜色
2. 翻转相邻格子的颜色(翻转：黑色变成白色，白色变成黑色；相邻：两个格子有公共边)
当然了，帕斯卡金魔力有限。你愿意告诉披荆斩棘、扫荡群魔的帕斯卡金如何施加最少次数的魔法让黑白广场变成纯白广场吗。

Input

多组数据，数据以两个空格隔开的0结束。
对于每组数据：
第一行包含两个整数N和M，表示广场规模为N行M列
第二行到第N+1行，每行包含M个字符，0为白色，1为黑色。

Output

对于每组数据，输出一行，包含一个整数，表示帕斯卡金施加魔法的最少次数。

Sample Input

3 3
111
111
111
3 3
000
010
000
0 0

Sample Output

3
2

Data Constraint

10%的数据满足：N*M<=12
30%的数据满足：N*M<=81
100%的数据满足：N,M<=10

Hint

本题打开O2优化开关,数据组数不超过10组。

样例解释：
111      011      001     000
111 ->  101 -> 010 -> 000
111      011      001     000

000     010     000
010 -> 111 -> 000
000     010     000

Solution

本题是轮廓线dp。

设f[ i ][ j ][S]表示做到第i行第j列轮廓线的状态为S的最小方案。

其中轮廓线表示第i行1~j-1这些数和第i-1行从j到m这些数的状态。

对于一个点的状态其实只有3种。

第一种：这个点没有操作且为0

第二种：这个点没有操作且为1

第三种：这个点操作了，不用记录是0还是1，因为两种操作其中一种就可以保证操作之后这个点一定变为0。

那么状压后，可以把第i行第j-1位看作最低位，而第i-1行第j列看作最高位，这样就方便转移。

我们从(i,j)转移到(i,j+1)，每次相当于把上一行的一个点删除，加入这一行的下一个点，并且保证了删掉的那个点变为0（或者说轮廓线以前的所有点都为0的方案数），同样是三种转移。

第一种：这个点（i，j+1）不操作，那么它不能影响周围的点，所有当且仅当（i-1，j）这个点不为1才能转移，花费为0。

第二种：这个点（i，j+1）操作，那么它能影响周围的点，注意更新（i，j）的状态，这种转移当且仅当（i-1，j）这个点为1，因为（i，j+1）这个点操作能够影响到（i-1，j+1）。花费为1。

第三种：这个点操作2次，将自己的颜色翻转，不会影响周围的点。花费为2。

注意对于每一行的最后一个点转移到下一行的时候要特殊处理（和转移到这一行的下一列分开处理）。

Code

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<cmath>
#define I int
#define ll long long
#define F(i,a,b) for(I i=a;i<=b;i++)
#define Fd(i,a,b) for(I i=a;i>=b;i--)
#define N 12
#define M 60000
using namespace std;
I n,m,ans,x,T,a[N][N],f[N][N][M],p[N],inf;
char c;
void R(I &x){
	x=0;c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
}
void work(){
	memset(f,127,sizeof f);inf=ans=f[0][0][0];
	f[1][1][(p[m]-1)/3*3+a[1][1]]=0;
	f[1][1][(p[m]-1)/3*3+1-a[1][1]]=2;
	f[1][1][p[m]-1]=1;
	F(i,1,n){
		F(j,1,m-1){
			F(S,0,p[m]-1) if(f[i][j][S]!=inf){
				x=a[i][j+1];
				if(S/p[m-1]==2&&i!=1) x^=1;
				if(S%3==2) x^=1;
				if(S/p[m-1]){
					T=S%p[m-1];
					if(S%3!=2) T=T/3*3+1-S%3;
					T=T*3+2;
					f[i][j+1][T]=min(f[i][j+1][T],f[i][j][S]+1);
				}
				if(S/p[m-1]!=1){
					T=S%p[m-1]*3+x;
					f[i][j+1][T]=min(f[i][j+1][T],f[i][j][S]);
					T=T-x+1-x;
					f[i][j+1][T]=min(f[i][j+1][T],f[i][j][S]+2);			
				}
			}
		}
		if(i==n) continue;
		F(S,0,p[m]-1) if(f[i][m][S]!=inf){
			x=a[i+1][1];
			if(S/p[m-1]==2) x^=1;
			if(S/p[m-1]){
				T=S%p[m-1]*3+2;
				f[i+1][1][T]=min(f[i+1][1][T],f[i][m][S]+1);
			}
			if(S/p[m-1]!=1){
				T=S%p[m-1]*3+x;
				f[i+1][1][T]=min(f[i+1][1][T],f[i][m][S]);
				T=T-x+1-x;
				f[i+1][1][T]=min(f[i+1][1][T],f[i][m][S]+2);
			}
		}
	}
	F(S,0,p[m]-1){
		x=S,T=0;
		while(x){
			T+=(x%3==1);
			x/=3;
		}
		if(!T) ans=min(ans,f[n][m][S]);
	}
}
I main(){
	freopen("square.in","r",stdin);
	freopen("square.out","w",stdout);
	p[0]=1;
	F(i,1,10) p[i]=p[i-1]*3;
	while(1){
		R(n),R(m);
		if(!n) return 0;
		F(i,1,n){
			F(j,1,m){
				c=getchar();
				while(c!='0'&&c!='1') c=getchar();
				a[i][j]=c-'0';
			}
		}
		work();
		printf("%d\n",ans);
	}
}

 

本文地址：https://blog.csdn.net/zsjzliziyang/article/details/107882426