新手新学插头DP,写炸

其中#9跑出来是负的..

已经和题解对照过几遍了(很可能哪里还没写好)

求助

//新手第一次打插头DP,参考了题解 (@y2823774827y 的)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=13;
const int mod=300017;
const int L=33554432;
int n,m,endx,endy,now,lst,ans;
int a[N][N],pow2[N+1],que[2][L],val[2][L],head[300055],next[L],cnt[2];
inline void read(int &x) {
	int tmp_read=0,nega=1;
	char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-')nega=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		tmp_read=tmp_read*10+c-'0';
		c=getchar();
	}
	x=tmp_read*nega;
	return ;
}
inline void ins(int bit,int v) {
	int u=bit%mod;
	for(register int i=head[u]; i!=0; i=next[i])
		if(que[now][i]==bit) {
			val[now][i]+=v;
			return ;
		}
	++cnt[now];
	next[cnt[now]]=head[u];
	head[u]=cnt[now];
	que[now][head[u]]=bit;
	val[now][head[u]]=v;
	return ;
}
signed main() {
//读入
	read(n),read(m);
//	scanf("%lld %lld",&n,&m);
	char cr=getchar();
	for(register int i=1; i<=n; ++i) {
		while(cr!='.'&&cr!='*')
			cr=getchar();
		for(register int u=1; u<=m; ++u) {
			if(cr=='.') {
				a[i][u]=1;
				endx=i,endy=u;
			}
			cr=getchar();
		}
	}
//初始化
	pow2[0]=1;
	for(register int i=1; i<=N; ++i)
		pow2[i]=pow2[i-1]<<2;
//	cnt[0]=1;
//	que[0][1]=0;
//	val[0][1]=1;
	ins(0,1);
//DP
	for(register int i=1; i<=n; ++i) {
		for(register int u=1; u<=cnt[now]; ++u)
			que[now][u]<<=2;
		for(register int u=1; u<=m; ++u) {
			//清空历史数据
			lst=now;
			now^=1;
			for(register int k=0; k<=300017; ++k) head[k]=0;
			cnt[now]=0;
			//DP
			for(register int k=1; k<=cnt[lst]; ++k) {
				int bit=que[lst][k];
				int num=val[lst][k];
				int ri=(bit>>((u-1)*2))%4,up=(bit>>(u*2))%4;
//				cout<<i<<' '<<u<<' '<<bit<<' '<<num<<endl;
				if(!a[i][u]) { //是障碍
					if(!ri&&!up)
						ins(bit,num);
				} else {
					if(!ri&&!up) {
						if(a[i+1][u]&&a[i][u+1])
							ins(bit+pow2[u-1]+pow2[u]*2,num);
					} else if(!ri&&up) {
						if(a[i+1][u])
							ins(bit-up*pow2[u]+up*pow2[u-1],num);
						if(a[i][u+1])
							ins(bit,num);
					} else if(ri&&!up) {
						if(a[i+1][u])
							ins(bit,num);
						if(a[i][u+1])
							ins(bit-ri*pow2[u-1]+ri*pow2[u],num);
					}  else {//两个要连起来
						if(ri==1&&up==1) { //改右边的插头
							int _change=1;
							for(int o=u+1; o<=m; ++o) {
								if((bit>>(o*2))%4==1)
									++_change;
								if((bit>>(o*2))%4==2)
									--_change;
								if(!_change) {
									ins(bit-pow2[u]-pow2[u-1]-pow2[o],num);//二改一
									break;
								}
							}
						} else if(ri==2&&up==2) { //改左边的插头
							int _change=1;
							for(int o=u-2; o>=0; --o) {
								if((bit>>(o*2))%4==1)
									--_change;
								if((bit>>(o*2))%4==2)
									++_change;
								if(!_change) {
									ins(bit-(pow2[u]*2)-(pow2[u-1]*2)+pow2[o],num);//一改二
									break;
								}
							}
						} else if(ri==2&&up==1) { //没有插头
							ins(bit-(pow2[u-1]*2)-pow2[u],num);
						} else if(i==endx&&u==endy) { //ri==1&&up==2 只能在终点成立
//							cout<<"~~~"<<num<<endl;
							ans+=num;
						}
					}
				}
			}
		}
	}
	printf("%lld\n",ans);
	return 0;
}