xixiup佬的代码过不了
查看原帖
xixiup佬的代码过不了
823227
lightmon楼主2023/11/15 22:27
#include <iostream>
#include <cstring>

#define int long long

using namespace std;

const int N = 14, Mod = 100003;

int n, m;
char ma[N][N];
int edx, edy;
int po[N];
int bg[Mod], dis[2][Mod], ne[Mod], cnt[2];
int val[2][Mod];
int now, pre;
int ans;

void init(){
    scanf("%lld%lld", &n, &m);
	for(int i=1;i<=n;i++){
        getchar();
		for (int j=1;j<=m;j++) {
            scanf("%c", &ma[i][j]);
			if (ma[i][j]=='.') {
				edx=i;
				edy=j;
            }
		}
	}
	po[0]=1;
	for(int j=1;j<=m;j++){
		po[j]=po[j-1]<<2;
	}
	return;
}

void update(int bit,int num){
	int bit1=bit%Mod+1;
	for(int i=bg[bit1];i;i=ne[i]){
		if(dis[now][i]==bit){
			val[now][i]+=num;
			return;
		}
	}
	cnt[now]++;
	ne[cnt[now]]=bg[bit1];
	bg[bit1]=cnt[now];
	dis[now][cnt[now]]=bit;
	val[now][cnt[now]]=num;
	return;
}

void work(){
	now=0,pre=1;
	update(0,1);
	for(int i=1;i<=n;i++){
		for(int q=1;q<=cnt[now];q++){
			dis[now][q]<<=2;
		}
		for(int j=1;j<=m;j++){
			memset(bg,0,sizeof(bg));
			swap(now,pre);
			cnt[now]=0;
			for(int q=1;q<=cnt[pre];q++){
				int bit=dis[pre][q],num=val[pre][q];
				int p1=(bit>>((j-1)*2))%4;
				int p2=(bit>>(j*2))%4;
				if(ma[i][j]=='*'){
					if(p1==0&&p2==0){
						update(bit,num);
					}
				}
				else if(p1==0&&p2==0){
					if(ma[i+1][j]=='.'&&ma[i][j+1]=='.'){
						update(bit+po[j-1]+po[j]*2,num);
					}
				}
				else if(p1==0&&p2!=0){
					if(ma[i+1][j]=='.'){
						update(bit-po[j]*p2+po[j-1]*p2,num);
					}
					if(ma[i][j+1]=='.'){
						update(bit,num);
					}
				}
				else if(p1!=0&&p2==0){
					if(ma[i+1][j]=='.'){
						update(bit,num);
					}
					if(ma[i][j+1]=='.'){
						update(bit-po[j-1]*p1+po[j]*p1,num);
					}
				}
				else if(p1!=0&&p2!=0){
					if(p1==1&&p2==1){
						int k=1;
						for(int q=j+1;q<=m;q++){
							if((bit>>(q*2))%4==1){
								k++;
							}
							if((bit>>(q*2))%4==2){
								k--;
							}
							if(k==0){
								update(bit-po[j-1]-po[j]-po[q],num);
								break;
							}
						}
					}
					else if(p1==2&&p2==2){
						int k=1;
						for(int q=j-2;q>=0;q--){
							if((bit>>(q*2))%4==1){
								k--;
							}
							if((bit>>(q*2))%4==2){
								k++;
							}
							if(k==0){
								update(bit-po[j-1]*2-po[j]*2+po[q],num);
								break;
							}
						}
					}
					else if(p1==2&&p2==1){
						update(bit-po[j-1]*2-po[j],num);
					}
					else{
						if(i==edx&&j==edy){
							ans+=num;
						}
					}
				}
			}
		}
	}
	printf("%lld\n",ans);
}


signed main() {
    init();
    work();
    return 0;
}
2023/11/15 22:27
加载中...