2331: [SCOI2011]地板

本文主要是介绍2331: [SCOI2011]地板，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

插头Dp

/**************************************************************Problem: 2331User: sxb_201Language: C++Result: AcceptedTime:980 msMemory:43148 kb
****************************************************************/#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define MO 20110520
int ans[5000000];
int f[700000],top;
int n,m;
char s[200][200];
bool ok(int x)
{for(int i=0;i<=m+1;i++){if( (x & (3<<(i*2)) )  ==(3<<(i*2))) return false;}return true;
}
int F(int x,int now,int up,int left)
{int tmp=(x>>(now*2))%4;tmp^=up;x^=( tmp<<(now*2) );x>>=2;x<<=2;x^=left;return x;
}
char a[200][200];
int g[5000000];
int main()
{cin >>n >>m;for(int i=1;i<=n;i++)scanf("%s",s[i]+1);if(n>=m)for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)a[i][j]=s[i][j];else{swap(n,m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)a[i][j]=s[j][i];}for(int i=0;i< (1<<((m+1)*2));i++){if(ok(i)) f[++top]=i;}ans[0]=1;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)if(a[i][j]!='*'){for(int k=1;k<=top;k++)g[f[k]]=0; for(int k=1;k<=top;k++){int tmp=f[k];if(ans[tmp]==0) continue;int left=tmp%4;int up=  ( tmp>>( j*2) )%4;int to; if(up==0&&left==0){to=F(tmp,j,0,2);g[to]=(g[to]+ans[tmp])%MO;to=F(tmp,j,2,0);g[to]=(g[to]+ans[tmp])%MO;to=F(tmp,j,1,1);g[to]=(g[to]+ans[tmp])%MO;}if(up==0&&left==1){to=F(tmp,j,0,0);g[to]=(g[to]+ans[tmp])%MO;to=F(tmp,j,0,1);g[to]=(g[to]+ans[tmp])%MO;}if(up==0&&left==2){to=F(tmp,j,0,2);g[to]=(g[to]+ans[tmp])%MO;to=F(tmp,j,1,0);g[to]=(g[to]+ans[tmp])%MO;}if(up==1&&left==0){to=F(tmp,j,0,0);g[to]=(g[to]+ans[tmp])%MO;to=F(tmp,j,1,0);g[to]=(g[to]+ans[tmp])%MO;          }if(up==1&&left==1){}if(up==1&&left==2){}if(up==2&&left==0){to=F(tmp,j,0,1);g[to]=(g[to]+ans[tmp])%MO;to=F(tmp,j,2,0);g[to]=(g[to]+ans[tmp])%MO;}if(up==2&&left==1){}if(up==2&&left==2){to=F(tmp,j,0,0);g[to]=(g[to]+ans[tmp])%MO;}   }//  memset(ans,0,sizeof(ans));for(int k=1;k<=top;k++)ans[f[k]]=g[f[k]];}else{for(int k=1;k<=top;k++)if(f[k]%4!=0||((f[k]>>(j*2))%4!=0))ans[f[k]]=0;}for(int k=1;k<=top;k++)if(f[k]%4!=0)ans[f[k]]=0;}cout<<ans[0]<<endl;return 0;
}

这篇关于2331: [SCOI2011]地板的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---