记录编号	88332	评测结果	AAA
题目名称	[UVa 11443] 网格里的树	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.759 s
提交时间	2014-02-19 20:14:48	内存使用	9.56 MiB

#include<iostream>
#include<cstdio>
#include<deque>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<vector>
using namespace std;
//本题中下标从0开始
const int SIZEN=200,SIZEM=8,HASHVAL=500013;
int N,M,MOD;
bool orih[SIZEN][SIZEM]={0};//一个点向左是否有连边
bool oriv[SIZEN][SIZEM]={0};//一个点向上是否有连边
/*状态储存的是从左到右八个点的连通状况,以最小表示法
每个点的最小表示法可能是0~7,用三个二进制位存放
这样总共是至多24个二进制位,用int可以存下
从低位到高位(从右到左)分别储存第0~M-1列的信息
*/
class STATE{
public:
	int comp[SIZEM];//连通块
	int numc[SIZEM];//每个连通块有多少
	void print(void){//调试接口,输出状态信息
		cout<<"comp:";for(int i=0;i<M;i++) cout<<comp[i]<<" ";cout<<endl;
		cout<<"numc:";for(int i=0;i<=M;i++) cout<<numc[i]<<" ";cout<<endl;
	}
	void clear(void){memset(comp,0,sizeof(comp));memset(numc,0,sizeof(numc));}//numc会在每次计算前清空,这里就不进行clear
	void calc_num(void){
		memset(numc,0,sizeof(numc));
		for(int i=0;i<M;i++) numc[comp[i]]++;
	}
	void remark(void){
		int atp[SIZEM+1]={0};
		memset(atp,-1,sizeof(atp));
		for(int i=0;i<M;i++){
			if(atp[comp[i]]==-1) atp[comp[i]]=i;
			comp[i]=atp[comp[i]];
		}
	}
	bool connect(int x,int y,bool up,bool left){
		//向上连和向左连的状态是up和left
		//本函数检查:①是否成环,②是否将上方格子独立,③是否连向边界
		//要求此时已经进行calc_num操作
		if(up&&x==0) return false;//连向边界
		if(left&&y==0) return false;//连向边界
		if(x&&!up&&numc[comp[y]]==1) return false;//将上方格子独立
		if(up&&left){//将左右连在一起
			if(comp[y]==comp[y-1]) return false;//成环
			int temp=comp[y];
			for(int i=0;i<M;i++){
				if(comp[i]==temp) comp[i]=comp[y-1];
			}
			remark();
			return true;
		}
		if(up) return true;//comp不变
		if(left){
			comp[y]=comp[y-1];
			remark();
			return true;
		}
		//单独一块
		comp[y]=M;
		remark();
		return true;
	}
	int mdl(void){
		int ans=0;
		for(int i=M-1;i>=0;i--){
			ans=(ans<<3)+comp[i];
		}
		return ans;
	}
	void demdl(int s){
		for(int i=0;i<M;i++){
			comp[i]=(s&7);
			s>>=3;
		}
	}
};
class HASHMAP{
public:
	int hash[HASHVAL];
	vector<pair<int,int> > st;//first是状态,second是个数
	int value(int s){
		int hashpos=s%HASHVAL;
		while(hash[hashpos]!=-1){
			if(st[hash[hashpos]].first==s) return st[hash[hashpos]].second;
			hashpos++;
			if(hashpos==HASHVAL) hashpos=0;
		}
		return -1;
	}
	void clear(void){
		memset(hash,-1,sizeof(hash));
		st.clear();
	}
	void insert(int s,int f){//给s状态加上f种
		if(st.size()>=HASHVAL){cout<<"hash overflow!"<<endl;}//卖个萌
		f%=MOD;
		int hashpos=s%HASHVAL;
		while(hash[hashpos]!=-1){
			if(st[hash[hashpos]].first==s){
				st[hash[hashpos]].second+=f;
				st[hash[hashpos]].second%=MOD;
				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;
	for(int i=0;i<F[k].st.size();i++){
		S.clear();
		S.demdl(F[k].st[i].first);
		S.calc_num();
		nowf=F[k].st[i].second;
		for(int up=oriv[x][y];up<=1;up++){
			for(int left=orih[x][y];left<=1;left++){
				T=S;
				if(T.connect(x,y,up,left)){
					F[k^1].insert(T.mdl(),nowf);
				}
			}
		}
	}
}
void work(void){
	int k=0;
	F[k].clear();
	F[k].insert(0,1);
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			update(k,i,j);
			k^=1;
		}
	}
	int ans=F[k].value(0);
	if(ans==-1) printf("Impossible\n");
	else printf("%d\n",ans);
}
void global_clear(void){
	memset(orih,0,sizeof(orih));
	memset(oriv,0,sizeof(oriv));
}
void read(void){
	scanf("%d%d%d",&N,&M,&MOD);
	string str;
	for(int i=0;i<2*N-1;i++){
		//getline(cin,str);//额...可能有空格
		cin>>str;
		for(int j=0;j<2*M-1;j++){
			if(!(i&1)&&!(j&1)) continue;//这会是一个'.'
			if(!(i&1)&&(j&1)) if(str[j]=='-') orih[i/2][(j+1)/2]=true;
			if((i&1)&&!(j&1)) if(str[j]=='|') oriv[(i+1)/2][j/2]=true;
			if((i&1)&&(j&1)) continue;//这会是一个' '
		}
	}
}
int main(){
	freopen("treeinagrid.in","r",stdin);
	freopen("treeinagrid.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T--){
		global_clear();
		read();
		work();
	}
	return 0;
}