记录编号	417502	评测结果	AAA
题目名称	[UVa 11443] 网格里的树	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	1.056 s
提交时间	2017-06-25 20:16:26	内存使用	9.55 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
int T,n,m,mod;
char s[410][20];
int inc(int x,int y){x+=y;return x>=mod?x-mod:x;}
struct state{
	int fa[8],size[8];
	void init(int S){
		for (int i=0;i<m;i++)
			size[i]=0;
		for (int i=0;i<m;i++){
			fa[i]=(S>>(i+i+i)&7);
			size[fa[i]]++;
		}
	}
	void remark(){
		static int Min[9];
		for (int i=0;i<=m;i++) Min[i]=-1;
		for(int i=0;i<m;i++){
			if(Min[fa[i]]==-1) Min[fa[i]]=i;
			fa[i]=Min[fa[i]];
		}
	}
	bool test(int x,int y,bool up,bool left){
		//判断该种连接方式是否合法 
		if (!x&&up) return 0;//连出边界 
		if (!y&&left) return 0;//连出边界 
		if (x&&!up&&size[fa[y]]==1) return 0;//上方的点孤立了 
		if (up&&left){
			if (fa[y-1]==fa[y]) return 0;//成环 
			int S=fa[y];fa[y]=fa[y-1];
			for (int i=0;i<m;i++)
				if (fa[i]==S) fa[i]=fa[y-1];
			remark();
			return 1;
		}
		if (up) return 1;
		if (left) fa[y]=fa[y-1];
			else fa[y]=m;
		remark();
		return 1;
	}
	int val(){
		int S=0;
		for (int i=0;i<m;i++) S|=fa[i]<<(i+i+i);
		return S;
	}
	void print(){
		for (int i=0;i<m;i++) printf("%d ",fa[i]);
	}
};
const int N=1e6+10;
struct hash_map{
	int q[N],val[N],key[N],size;
	hash_map(){memset(key,-1,sizeof key);}
	int hash(int x){
		int ans=0;
		for (int i=x;i;i/=13) ans=ans*23+i%13;
		ans%=N;
		if (ans<0) ans+=N;
		while (key[ans]!=-1&&key[ans]!=x) ans==N-1?ans=0:ans++;
		return ans;
	}
	bool count(int x){
		return key[hash(x)]!=-1;
	}
	int& operator [] (int x){
		int ans=hash(x);
		if (key[ans]==-1){
			key[ans]=x;
			q[++size]=ans;
			val[ans]=0;
		}
		return val[ans];
	}
	void clear(){
		while (size) key[q[size--]]=-1;
	}
};
typedef pair<int,int> pii;
struct table{
	hash_map M;
	//map<int,int> M;
	vector<pii> v;//first表示其状态,second为方案数 
	void clear(){
		M.clear();
		v.clear();
	}
	void insert(int S,int k){//给S状态方案数+k 
		if (!M.count(S)){
			M[S]=v.size();
			v.push_back(pii(S,k));
		}
		else{
			int &val=v[M[S]].second;
			val=inc(val,k);
		}
	}
	int val(int S){
		if (!M.count(S)) return 0;
		return v[M[S]].second;
	}
}dp[2],*x=&dp[0],*y=&dp[1];
bool left_edge[210][20],up_edge[210][20];
void extend(int i,int j){
	y->clear();
	state S,T;
	for (int a=0;a<x->v.size();a++){
		S.init(x->v[a].first);
		int val=x->v[a].second;
		for (int up=up_edge[i][j];up<=1;up++)
		for (int left=left_edge[i][j];left<=1;left++){
			T=S;
			if (T.test(i,j,up,left))
				y->insert(T.val(),val);
		}
	}
	swap(x,y);
	/*printf("add (%d,%d)\n",i,j);
	for (int i=0;i<x->v.size();i++){
		S.init(x->v[i].first);
		S.print();
		printf("cases: %d\n",x->v[i].second);
	}*/
}
int main()
{
	freopen("treeinagrid.in","r",stdin);
	freopen("treeinagrid.out","w",stdout);
	scanf("%d",&T);
	while (T--){
		scanf("%d%d%d",&n,&m,&mod);
		memset(s,0,sizeof s);
		for (int i=0;i<n*2-1;i++) scanf("%s",s[i]);
		for (int i=0;i<n;i++)
		for (int j=0;j<m;j++){
			left_edge[i][j+1]=(s[i<<1][j<<1|1]=='-');
			up_edge[i+1][j]=(s[i<<1|1][j<<1]=='|');
		}
		x->clear();
		x->insert(0,1);
		for (int i=0;i<n;i++)
		for (int j=0;j<m;j++)
			extend(i,j);
		if (!x->M.count(0)) puts("Impossible");
			else printf("%d\n",x->val(0));
	}
	return 0;
}