【FZU】1977 Pandora adventure

      #include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;



typedef long long ll;

struct H {

	static const int M=799997;

	struct E { int next, to; }e[M];

	int ihead, cnt, hash[M];

	ll sum[M];

	H() { ihead=cnt=0; memset(hash, -1, sizeof hash); memset(sum, 0, sizeof sum); }

	bool find(int x, int &pos) {

		pos=x%M;

		while(1) { if(hash[pos]==x) return false; if(hash[pos]==-1) break; ++pos; if(pos==M) pos=0; }

		hash[pos]=x; return true;

	}

	void ins(int a, ll b) {

		int pos; if(!find(a, pos)) { sum[pos]+=b; return; }

		e[++cnt].next=ihead; ihead=cnt; e[cnt].to=pos; sum[pos]=b;

	}

	void clr() { for(int i=ihead; i; i=e[i].next) hash[e[i].to]=-1, sum[e[i].to]=0; ihead=cnt=0; }

}T1, T2;



#define BIT(a,b) ((a)<<((b)<<1))

#define CLR(a,b) (a^=((a)&BIT(3,b)))

#define GET(a,b) (3&((a)>>((b)<<1)))



const int N=15;

int n, m, all;

ll ans;

int mp[N][N];



int find(int s, int col, int flag) {

	int sum=0;

	if(flag) {

		for(int i=col; i<=m; ++i) {

			int k=GET(s, i);

			if(k==1) ++sum;

			if(k==2) --sum;

			if(!sum) return i;

		}

	}

	else {

		for(int i=col; i>=0; --i) {

			int k=GET(s, i);

			if(k==1) --sum;

			if(k==2) ++sum;

			if(!sum) return i;

		}

	}

	return -1;

}

void print(int s) {

	for(int i=0; i<=m; ++i) { int k=GET(s, i); if(k==0) putchar('#'); else if(k==1) putchar('('); else if(k==2) putchar(')');  }

	puts("");

}

#define F puts("error");

bool next(int s, int row, int col, bool U, bool D, bool L, bool R, int &t) {

	if((row==n-1&&D) || (row==0&&U) || (col==m-1&&R) || (col==0&&L)) return 0;

	if((D&&!mp[row+1][col]) || (R&&!mp[row][col+1])) return 0;

	int l=GET(s, col), u=GET(s, col+1), flag=GET(s, m+1), d=0, r=0;

	if((l&&!L) || (!l&&L) || (u&&!U) || (!u&&U)) return 0;

	// printf("State:"); print(s);

	// printf("row:%d, col:%d, U:%d, D:%d, L:%d, R:%d ", row, col, U, D, L, R);

	// printf(" left:"); if(l==1) printf("("); if(l==2) printf(")"); if(l==0) printf("#");

	// printf(" uptp:"); if(u==1) printf("("); if(u==2) printf(")"); if(u==0) printf("#"); puts("");

	t=s;

	CLR(t, col);

	CLR(t, col+1);

	if(!l && !u) {

		if(R && D) d=1, r=2;

	}

	else if(l && u) {

		if(l==1 && u==1) {

			int pos=find(s, col+1, 1);

			CLR(t, pos);

			t|=BIT(1, pos);

		}

		else if(l==2 && u==2) {

			int pos=find(s, col, 0);

			CLR(t, pos);

			t|=BIT(2, pos);

		}

		else if(l==1 && u==2) flag=1;

	}

	else if(l && !u) {

		if(D) d=l, r=0;

		if(R) d=0, r=l;

	}

	else if(!l && u) {

		if(D) d=u, r=0;

		if(R) d=0, r=u;

	}

	t|=BIT(d, col);

	t|=BIT(r, col+1);

	if(col==m-1) t<<=2; //puts("=============\nnext");  print(t);

	t&=all;

	if(flag) t|=BIT(1, m+1);

	return 1;

}



void bfs() {

	H *q1, *q2;

	q1=&T1; q2=&T2;

	q1->clr();

	q2->clr();

	q1->ins(0, 1);

	for(int row=0; row<n; ++row) for(int col=0; col<m; ++col) {

		q2->clr(); //printf("q1->cnt:%d\n", q1->cnt);

		for(int i=q1->ihead; i; i=q1->e[i].next) {

			int s=q1->hash[q1->e[i].to], t, flag=GET(s, m+1); //print(s);

			ll sum=q1->sum[q1->e[i].to];

			if(mp[row][col]==2 && flag) continue;

			if(mp[row][col]<=1) { if(next(s, row, col, 0, 0, 0, 0, t)) q2->ins(t, sum); }

			if(mp[row][col]>=1 && !flag) { //忘记判flag又调了好久...

				if(next(s, row, col, 1, 1, 0, 0, t)) q2->ins(t, sum);

				if(next(s, row, col, 1, 0, 1, 0, t)) q2->ins(t, sum);

				if(next(s, row, col, 1, 0, 0, 1, t)) q2->ins(t, sum);

				if(next(s, row, col, 0, 1, 1, 0, t)) q2->ins(t, sum);

				if(next(s, row, col, 0, 1, 0, 1, t)) q2->ins(t, sum);

				if(next(s, row, col, 0, 0, 1, 1, t)) q2->ins(t, sum);

			}

		}

		swap(q1, q2);

	}

	for(int i=q1->ihead; i; i=q1->e[i].next) ans+=q1->sum[q1->e[i].to];

}



int main() {

	int cs; scanf("%d", &cs);

	char s[N];

	for(int cc=1; cc<=cs; ++cc) {

		ans=0;

		scanf("%d%d", &n, &m); all=BIT(1, m+1)-1;

		for(int i=0; i<n; ++i) {

			scanf("%s", s);

			for(int j=0; j<m; ++j) {

				if(s[j]=='*') mp[i][j]=1;

				else if(s[j]=='O') mp[i][j]=2;

				else mp[i][j]=0;

			}

		}

		bfs();

		printf("Case %d: %I64d\n", cc, ans);

	}

	return 0;

}