Problem 1059 : Mysterious Onslaught

解法

4行分について解を全生成しておく。状態数2^20(=100万)のBFSなので間に合う。
残り1行分については探索する。


探索は下5マスについて、これを角にするように書ける長方形を全部書いていく(25通りx20x15x10x5)
この探索において、同じマスを始点にする二つの長方形があることは考えなくてよい。
(たとえば、一番左下を含むような5x5と3x3の長方形を取る場合というのは、
2x3と2x2の長方形に分解できるので)

ソースコード

unsigned char cost[1<<20];
int mask[5][5][6][6];
void gen(){
	memset(cost,-1,sizeof(cost));
	cost[0]=0;
	rep(i,5)rep(j,5)for(int h=1;h<=5-i;h++)for(int w=1;w<=5-j;w++){
		int m=(1<<w)-1;
		rep(k,h)mask[i][j][h][w]^=m<<(i+k)*5+j;
	}
	queue<int> Q; Q.push(0); int cnt=0;
	while(!Q.empty()){
		int c=Q.front(),cc=cost[c]; Q.pop();
		rep(i,4)rep(j,5)for(int h=1;h<=4-i;h++)for(int w=1;w<=5-j;w++){
			int nc=c^mask[i][j][h][w];
			if(cost[nc]>cc+1)cost[nc]=cc+1,Q.push(nc);
		}
	}
}
int lim;
int getcost(int c){
	int ret=cost[c&(1<<20)-1],bit=0;
	for(c>>=20;c;c&=c-1)bit++;
	return ret+min(bit,6-bit);
}
void rec(int c,int x,int cnt){
	if(c>>20==0)lim=min(lim,cost[c]+cnt);
	if(x>=5)return;
	
	rep(i,5)for(int j=x;j<5;j++){
		int nc=c^mask[i][x][5-i][j-x+1];
		if(!(nc&1<<20+x))rec(nc,x+1,cnt+1);
	}
	if(!(c&1<<20+x))rec(c,x+1,cnt);
}
int solve(int c){
	lim=getcost(c);
	rec(c,0,0);
	return lim;
}
int main(){
	gen();
	
	int n,ans;
	while(cin>>n,n){
		int c=0,t;
		rep(i,n)rep(j,n){
			cin>>t;
			if(t)c^=1<<i*5+j;
		}
		ans=n<5?cost[c]:solve(c);
		rep(i,ans)cout<<"myon"; cout<<endl;
	}
	return 0;
}