2114-Median Filter - 眠いのです

問題概要

黒と白のみから構成された画像にメディアンフィルターを掛けたものが与えられる．
元の画像として考えられるもののうち，黒の個数が最大のものと最小のものの差を答えろ．
メディアンフィルターの詳細はhttp://en.wikipedia.org/wiki/Median_filterより．
解法

前(W*2+2)マスを保持するBitDP．
計算量は W * H * 2^((W+1)*2) ぐらいになる．
DP配列の初期化をmemsetで行なうとTLEする．
実装(C++)

#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>
#include <boost/format.hpp>
using namespace std;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=(x);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)

int dx[9]={-1,0,1,0,-1,-1,1,1,0},dy[9]={0,-1,0,1,1,-1,1,-1,0};

int W,H;
int MAP[8][8];
int ROW[8];
typedef char DP_TYPE;
DP_TYPE DP_MAX[1<<18][8][8];
DP_TYPE DP_MIN[1<<18][8][8];
int mask;

int get_data(int back,int x,int y,int sx,int sy,int now){
	if(sy<0)sy=0;
	if(sx<0)sx=0;
	if(sx>=W)sx=W-1;
	if(sy>=H)sy=H-1;
	int cnt=(y-sy)*W+x-sx-1;
	if(cnt>=0&&cnt<2*W+2){
		return (back>>cnt)&1;
	}
	if(cnt==-1)return now;
}
//周辺の黒の個数を数える
int count(int back,int x,int y,int sx,int sy,int now){
	int res=0;
	for(int i=0;i<9;i++){
		res+=get_data(back,x,y,sx+dx[i],sy+dy[i],now);
	}
	return res;
}
DP_TYPE solve(int back,int x,int y){
	if(y==H)return 0;
	DP_TYPE &ret=DP_MIN[back][x][y];
	int nx=x+1,ny=y;
	if(nx>=W){
		ny+=1;nx=0;
	}
	if(ret==0x7F){
		//このマスに置くか置かないか
		ret=0x7E;
		if(y==0&&H!=1){
			ret=min<DP_TYPE>(ret,solve((((back)<<1)|0)&mask,nx,ny));
			if(solve((((back)<<1)|1)&mask,nx,ny)<0x7E)ret=min<DP_TYPE>(ret,solve((((back)<<1)|1)&mask,nx,ny)+1);
		}else if(y<H-1||H==1){
			if(x==0&&W!=1){
				ret=min<DP_TYPE>(ret,solve(((back<<1)|0)&mask,nx,ny));
				if(solve(((back<<1)|1)&mask,nx,ny)<0x7E)ret=min<DP_TYPE>(ret,solve(((back<<1)|1)&mask,nx,ny)+1);
			}else if(x<W-1||W==1){
				int sx=x-1;
				int sy=y-1;
				if(sx<0)sx=0;if(sy<0)sy=0;
				if(MAP[sx][sy]==count(back,x,y,sx,sy,0)/5){
					ret=min<DP_TYPE>(ret,solve(((back<<1)|0)&mask,nx,ny));
				}
				if(MAP[sx][sy]==count(back,x,y,sx,sy,1)/5){
					if(solve(((back<<1)|1)&mask,nx,ny)<0x7E)ret=min<DP_TYPE>(ret,solve(((back<<1)|1)&mask,nx,ny)+1);
				}
			}else{
				int sx=x-1;
				int sy=y-1;
				if(sx<0)sx=0;if(sy<0)sy=0;
				if(MAP[sx][sy]==count(back,x,y,sx,sy,0)/5&&MAP[sx+1][sy]==count(back,x,y,sx+1,sy,0)/5){
					ret=min<DP_TYPE>(ret,solve(((back<<1)|0)&mask,nx,ny));
				}
				if(MAP[sx][sy]==count(back,x,y,sx,sy,1)/5&&MAP[sx+1][sy]==count(back,x,y,sx+1,sy,1)/5){
					if(solve(((back<<1)|1)&mask,nx,ny)<0x7E)ret=min<DP_TYPE>(ret,solve(((back<<1)|1)&mask,nx,ny)+1);
				}
			}
		}else{
			if(x==0&&W!=1){
				ret=min<DP_TYPE>(ret,solve(((back<<1)|0)&mask,nx,ny));
				if(solve(((back<<1)|1)&mask,nx,ny)<0x7E)ret=min<DP_TYPE>(ret,solve(((back<<1)|1)&mask,nx,ny)+1);
			}else if(x<W-1||W==1){
				int sx=x-1;
				int sy=y-1;
				if(sx<0)sx=0;if(sy<0)sy=0;
				if(MAP[sx][sy]==count(back,x,y,sx,sy,0)/5&&MAP[sx][sy+1]==count(back,x,y,sx,sy+1,0)/5){
					ret=min<DP_TYPE>(ret,solve(((back<<1)|0)&mask,nx,ny));
				}
				if(MAP[sx][sy]==count(back,x,y,sx,sy,1)/5&&MAP[sx][sy+1]==count(back,x,y,sx,sy+1,1)/5){
					if(solve(((back<<1)|1)&mask,nx,ny)<0x7E)ret=min<DP_TYPE>(ret,solve(((back<<1)|1)&mask,nx,ny)+1);
				}
			}else{
				int sx=x-1;
				int sy=y-1;
				if(sx<0)sx=0;if(sy<0)sy=0;
				if(MAP[sx][sy]==count(back,x,y,sx,sy,0)/5&&MAP[sx][sy+1]==count(back,x,y,sx,sy+1,0)/5&&MAP[sx+1][sy+1]==count(back,x,y,sx+1,sy+1,0)/5&&MAP[sx+1][sy]==count(back,x,y,sx+1,sy,0)/5){
					ret=min<DP_TYPE>(ret,solve(((back<<1)|0)&mask,nx,ny));
				}
				if(MAP[sx][sy]==count(back,x,y,sx,sy,1)/5&&MAP[sx][sy+1]==count(back,x,y,sx,sy+1,1)/5&&MAP[sx+1][sy+1]==count(back,x,y,sx+1,sy+1,1)/5&&MAP[sx+1][sy]==count(back,x,y,sx+1,sy,1)/5){
					if(solve(((back<<1)|1)&mask,nx,ny)<0x7E)ret=min<DP_TYPE>(ret,solve(((back<<1)|1)&mask,nx,ny)+1);
				}
			}
		}
		//cout<<boost::format("%d,%d,%d:%d\n")%back%x%y%(int)ret;
	}
	return ret;
}
DP_TYPE solve2(int back,int x,int y){
	if(y==H)return 0;
	DP_TYPE &ret=DP_MAX[back][x][y];
	int nx=x+1,ny=y;
	if(nx>=W){
		ny+=1;nx=0;
	}
	if(ret==-1){
		//このマスに置くか置かないか
		ret=-2;
		if(y==0&&H!=1){
			ret=max<DP_TYPE>(ret,solve2((((back)<<1)|0)&mask,nx,ny));
			if(solve2((((back)<<1)|1)&mask,nx,ny)>=0)ret=max<DP_TYPE>(ret,solve2((((back)<<1)|1)&mask,nx,ny)+1);
		}else if(y<H-1||H==1){
			if(x==0&&W!=1){
				ret=max<DP_TYPE>(ret,solve2(((back<<1)|0)&mask,nx,ny));
				if(solve2(((back<<1)|1)&mask,nx,ny)>=0)ret=max<DP_TYPE>(ret,solve2(((back<<1)|1)&mask,nx,ny)+1);
			}else if(x<W-1||W==1){
				int sx=x-1;
				int sy=y-1;
				if(sx<0)sx=0;if(sy<0)sy=0;
				if(MAP[sx][sy]==count(back,x,y,sx,sy,0)/5){
					ret=max<DP_TYPE>(ret,solve2(((back<<1)|0)&mask,nx,ny));
				}
				if(MAP[sx][sy]==count(back,x,y,sx,sy,1)/5){
					if(solve2(((back<<1)|1)&mask,nx,ny)>=0)ret=max<DP_TYPE>(ret,solve2(((back<<1)|1)&mask,nx,ny)+1);
				}
			}else{
				int sx=x-1;
				int sy=y-1;
				if(sx<0)sx=0;if(sy<0)sy=0;
				if(MAP[sx][sy]==count(back,x,y,sx,sy,0)/5&&MAP[sx+1][sy]==count(back,x,y,sx+1,sy,0)/5){
					ret=max<DP_TYPE>(ret,solve2(((back<<1)|0)&mask,nx,ny));
				}
				if(MAP[sx][sy]==count(back,x,y,sx,sy,1)/5&&MAP[sx+1][sy]==count(back,x,y,sx+1,sy,1)/5){
					if(solve2(((back<<1)|1)&mask,nx,ny)>=0)ret=max<DP_TYPE>(ret,solve2(((back<<1)|1)&mask,nx,ny)+1);
				}
			}
		}else{
			if(x==0&&W!=1){
				ret=max<DP_TYPE>(ret,solve2(((back<<1)|0)&mask,nx,ny));
				if(solve2(((back<<1)|1)&mask,nx,ny)>=0)ret=max<DP_TYPE>(ret,solve2(((back<<1)|1)&mask,nx,ny)+1);
			}else if(x<W-1||W==1){
				int sx=x-1;
				int sy=y-1;
				if(sx<0)sx=0;if(sy<0)sy=0;
				if(MAP[sx][sy]==count(back,x,y,sx,sy,0)/5&&MAP[sx][sy+1]==count(back,x,y,sx,sy+1,0)/5){
					ret=max<DP_TYPE>(ret,solve2(((back<<1)|0)&mask,nx,ny));
				}
				if(MAP[sx][sy]==count(back,x,y,sx,sy,1)/5&&MAP[sx][sy+1]==count(back,x,y,sx,sy+1,1)/5){
					if(solve2(((back<<1)|1)&mask,nx,ny)>=0)ret=max<DP_TYPE>(ret,solve2(((back<<1)|1)&mask,nx,ny)+1);
				}
			}else{
				int sx=x-1;
				int sy=y-1;
				if(sx<0)sx=0;if(sy<0)sy=0;
				if(MAP[sx][sy]==count(back,x,y,sx,sy,0)/5&&MAP[sx][sy+1]==count(back,x,y,sx,sy+1,0)/5&&MAP[sx+1][sy+1]==count(back,x,y,sx+1,sy+1,0)/5&&MAP[sx+1][sy]==count(back,x,y,sx+1,sy,0)/5){
					ret=max<DP_TYPE>(ret,solve2(((back<<1)|0)&mask,nx,ny));
				}
				if(MAP[sx][sy]==count(back,x,y,sx,sy,1)/5&&MAP[sx][sy+1]==count(back,x,y,sx,sy+1,1)/5&&MAP[sx+1][sy+1]==count(back,x,y,sx+1,sy+1,1)/5&&MAP[sx+1][sy]==count(back,x,y,sx+1,sy,1)/5){
					if(solve2(((back<<1)|1)&mask,nx,ny)>=0)ret=max<DP_TYPE>(ret,solve2(((back<<1)|1)&mask,nx,ny)+1);
				}
			}
		}
	}
	return ret;
}
bool input(){
	cin>>W>>H;
	if(W==0&&H==0)return false;
	for(int i=0;i<H;i++){
		ROW[i]=0;
		string in;
		cin>>in;
		for(int j=0;j<W;j++){
			MAP[j][i]=(in[j]=='#');
			if(in[j]=='#')ROW[i]|=1<<j;
		}
	}
	return true;
}
void initdp(){
	for(int i=0;i<(1<<(W*2+2));i++){
		for(int j=0;j<W;j++){
			for(int k=0;k<H;k++){
				DP_MAX[i][j][k]=0xFF;
				DP_MIN[i][j][k]=0x7F;
			}
		}
	}
}
int t=0;
int main(){
	while(input()){

		//DP配列の初期化
		initdp();

		mask=(1LL<<((W+1)*2))-1;

		int rm=solve2(0,0,0);
		if(rm<0||solve(0,0,0)>=0x7E){
			cout<<boost::format("Case %d: Impossible")%++t<<endl;
			continue;
		}
		cout<<boost::format("Case %d: %d")%++t%(int)(rm-solve(0,0,0))<<endl;
	}
	return 0;
}