记录编号	88681	评测结果	AAAAAAAAAA
题目名称	[UVa 1501] 修建长城	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.125 s
提交时间	2014-02-23 15:25:23	内存使用	0.41 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<vector>
using namespace std;
typedef long long ll;
const int SIZEN=12,HASHVAL=13131,INF=0x7fffffff;
char board[SIZEN][SIZEN]={0};
int N,M;
int lastx,lasty;
int ans;
//状态是:轮廓线上M+1个格子(含当前格子的左上格子)的连通性,用最小表示法
//每个格子的最小表示法用四个bit,这样总共是36个bit
//下标大的在高位,下标小的在低位
//本题下标从1开始
class STATE{
public:
	int comp[SIZEN];
	int ncomp[SIZEN];
	void clear(void){memset(comp,0,sizeof(comp));}
	void print(void){for(int i=1;i<=M+1;i++){cout<<comp[i]<<" ";}}
	int num_comp(void){//连通块的总数
		bool flag[SIZEN+3]={0};
		int num=0;
		for(int i=1;i<=M+1;i++){
			if(comp[i]&&!flag[comp[i]]) flag[comp[i]]=true,num++;
		}
		return num;
	}
	void calc_num(int y){//计算ncomp,保证comp中是正确的,其中comp[y]不计
		memset(ncomp,0,sizeof(ncomp));
		for(int i=1;i<=M+1;i++) if(i!=y) ncomp[comp[i]]++;
	}
	void nextline(void){//从行末转换到行首
		for(int i=M+1;i>1;i--) comp[i]=comp[i-1];
		comp[1]=0;
	}
	ll mdl(void){//调制成一个整数
		ll ans=0;
		for(int i=M+1;i>=1;i--) ans=(ans<<4)+comp[i];
		return ans;
	}
	void demdl(ll s){//把整数解调
		for(int i=1;i<=M+1;i++) comp[i]=s&15,s>>=4;
	}
	void merge(int a,int b){//把编号为b的连通块并入编号为a的连通块
		if(a==b) return;
		if(b<a) swap(a,b);//把编号较大的并入编号较小的
		for(int i=1;i<=M+1;i++) if(comp[i]==b) comp[i]=a;
	}
	void remark(void){//将comp改成最小表示法,即重新给分量标号
		int atp[SIZEN+3]={0};
		memset(atp,-1,sizeof(atp));
		for(int i=1;i<=M+1;i++){
			if(comp[i]==0) continue;
			if(atp[comp[i]]==-1) atp[comp[i]]=i;
			comp[i]=atp[comp[i]];
		}
	}
	bool placeblock(int x,int y,bool opt,int &dta){//决定第x行y列的格子,opt=1是放,opt=0是不放
		//不能放返回false,否则返回true并对状态进行相应改动,增加的长度是dta
		//左:y-1,左上:y,上:y+1,右上:y+2
		int l=y>1?comp[y-1]:0;//左
		int lu=comp[y];//左上
		int u=comp[y+1];//上
		int ru=l<M?comp[y+2]:0;//右上
		if(!opt){//选择了不放
			if(board[x][y]=='o') return false;
			if(l&&u&&!lu) return false;
			if(u&&ncomp[u]==1&&!(x>=lastx&&y>=lasty&&num_comp()==1)) return false;
			//将上方连通块独立,但若所有城市均被覆盖而且已经是符合题意的简单多边形那么可以将其独立掉
			dta=0;
			comp[y]=0;
			remark();
		}
		else{//选择了放
			if(board[x][y]=='x') return false;
			if(l&&u&&l==u&&!lu) return false;//中间出现了空洞
			if(lu&&!l&&!u) return false;//多边形的边界自交
			dta=4;if(u) dta-=2;if(l) dta-=2;//增加的边数
			comp[y]=M+2;
			if(u) merge(u,comp[y]);
			if(l) merge(l,comp[y]);
			remark();
		}
		return true;
	}
};
class HASHMAP{
public:
	int hash[HASHVAL];
	vector<pair<ll,int> > st;
	void clear(void){
		memset(hash,-1,sizeof(hash));
		st.clear();
	}
	void insert(ll s,int f){
		if(st.size()>=HASHVAL){cout<<"hash overflow!"<<endl;}
		int hashpos=s%HASHVAL;
		while(hash[hashpos]!=-1){
			if(st[hash[hashpos]].first==s){
				st[hash[hashpos]].second=min(st[hash[hashpos]].second,f);
				return;
			}
			hashpos++;
			if(hashpos==HASHVAL) hashpos=0;
		}
		hash[hashpos]=st.size();
		st.push_back(make_pair(s,f));
	}
};
HASHMAP F[2];
void update(int k,int x,int y){//用F[k]去更新F[k^1],其中新加的一格是(x,y)
	F[k^1].clear();
	STATE S,T;
	int nowf,incf;
	for(int i=0;i<F[k].st.size();i++){
		S.demdl(F[k].st[i].first);
		if(y==1) S.nextline();
		S.calc_num(y);
		nowf=F[k].st[i].second;
		for(int j=0;j<=1;j++){
			T=S;
			if(T.placeblock(x,y,j,incf)){
				F[k^1].insert(T.mdl(),nowf+incf);
			}
		}
	}
}
bool legalend(ll s){
	STATE S;
	S.demdl(s);
	return S.num_comp()<=1;
}
int kase=0;
void work(void){
	int k=0;
	F[k].clear();
	F[k].insert(0,0);//没有连通块
	for(int i=1;i<=N;i++){
		for(int j=1;j<=M;j++){
			update(k,i,j);
			k^=1;
		}
	}
	ans=INF;
	for(int i=0;i<F[k].st.size();i++){
		if(legalend(F[k].st[i].first)) ans=min(ans,F[k].st[i].second);
	}
	if(ans==INF) ans=-1;
	printf("Case #%d: %d\n",++kase,ans);
}
void read(void){
	scanf("%d%d",&N,&M);
	string str;
	for(int i=1;i<=N;i++){
		cin>>str;
		for(int j=1;j<=M;j++){
			board[i][j]=str[j-1];
			if(board[i][j]=='o') lastx=i,lasty=j;
		}
	}
}
int main(){
	freopen("constructthegreatwall.in","r",stdin);
	freopen("constructthegreatwall.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T--){
		read();
		work();
	}
	return 0;
}