Description
一个\(2*n\)的方格矩阵，每个格子里有一个字符
给定一个长度为\(m\)的字符串\(s\)
求在方格矩阵中，有多少种走法能走出字符串\(s\)
一种合法的走法定义为：从任意一个位置出发，每次只能走到相邻的格子(common side)，一个格子不能经过多次
\(n,m\le 2000\)
Analysis
刚做完一道百度之星题，跟这题很像，都是一个\(n^2\)的dp
考虑从一个格子出发的走法：
比如一开始往右走，走若干步，往下，设当前走了\(k\)步
此时如果往右走，那么左边有一堵墙，还需走后\(m-k\)步
如果往左，就只能一直往左，走到中途匹配完，或者走回到起点的下面，然后往左走一步，那么右边有一堵墙，还需走后\(m-2k\)步
一开始往下走或往左走同理，都能经过一些简单的转化最后变成一个有墙的问题
而对于有墙的问题，dp就没有后效性了，一个简单的dp即可
我们求出每个格子出发，左边有墙的，走完后\(k\)的字符的方案数，往左出发同理求
最后在扫一遍统计从每个格子出发的方案数
字符串匹配用hash即可
Code
#include#include #include #include #include #include using namespace std;typedef long long LL;typedef unsigned long long ull;const int M=2e3+7;const int Q=1e9+7;inline int pls(int x,int y){return (x+y)%Q;}inline int mns(int x,int y){return pls(x,Q-y);}inline int mul(int x,int y){return 1LL*x*y%Q;}int n,m;char s[2][M],t[M];int l[M][2][M],r[M][2][M];bool bl[M][2][M],br[M][2][M];struct Hsh{ static const int W=131; ull lf[M],rt[M],pw[M]; ull lfhsh(int x,int len){ int y=x+len-1; return lf[y]-lf[x-1]*pw[len]; } ull rthsh(int len,int y){ int x=y-len+1; return rt[x]-rt[y+1]*pw[len]; } void init(char *s,int n){ int i; for (pw[0]=1,i=1;i<=n;++i) pw[i]=pw[i-1]*W; for (lf[0]=0,i=1;i<=n;++i) lf[i]=lf[i-1]*W + s[i]-'a'; for (rt[n+1]=0,i=n;i>0;--i) rt[i]=rt[i+1]*W + s[i]-'a'; }}hs[2],ht;void solve(){ int i,j,k; for(i=n;i>0;--i) for(j=0;j<2;++j) for(k=2;k<=m;k+=2) br[i][j][k]= (i+k/2-1<=n && hs[j].lfhsh(i,k/2)==ht.lfhsh(m-k+1,k/2) && hs[j^1].rthsh(k/2,i+k/2-1)==ht.lfhsh(m-k/2+1,k/2)); for(i=1;i<=n;++i) for(j=0;j<2;++j) for(k=2;k<=m;k+=2) bl[i][j][k]= (i-k/2+1>=1 && hs[j].rthsh(k/2,i)==ht.lfhsh(m-k+1,k/2) && hs[j^1].lfhsh(i-k/2+1,k/2)==ht.lfhsh(m-k/2+1,k/2)); r[n+1][0][0]=r[n+1][1][0]=1; for(i=n;i>0;--i) for(j=0;j<2;++j) for(r[i][j][0]=1,k=1;k<=m;++k){ if(s[j][i]==t[m-k+1]) r[i][j][k]=pls(r[i][j][k],r[i+1][j][k-1]); if(k>2 && s[j][i]==t[m-k+1] && s[j^1][i]==t[m-k+2]) r[i][j][k]=pls(r[i][j][k],r[i+1][j^1][k-2]); if(br[i][j][k]) r[i][j][k]=pls(r[i][j][k],1); } l[0][0][0]=l[0][1][0]=1; for(i=1;i<=n;++i) for(j=0;j<2;++j) for(l[i][j][0]=1,k=1;k<=m;++k){ if(s[j][i]==t[m-k+1]) l[i][j][k]=pls(l[i][j][k],l[i-1][j][k-1]); if(k>2 && s[j][i]==t[m-k+1] && s[j^1][i]==t[m-k+2]) l[i][j][k]=pls(l[i][j][k],l[i-1][j^1][k-2]); if(bl[i][j][k]) l[i][j][k]=pls(l[i][j][k],1); } for(i=n;i>0;--i) for(j=0;j<2;++j) for(k=2;k<=m;k+=2) br[i][j][k]= (i+k/2-1<=n && hs[j].lfhsh(i,k/2)==ht.lfhsh(1,k/2) && hs[j^1].rthsh(k/2,i+k/2-1)==ht.lfhsh(k/2+1,k/2)); for(i=1;i<=n;++i) for(j=0;j<2;++j) for(k=2;k<=m;k+=2) bl[i][j][k]= (i-k/2+1>=1 && hs[j].rthsh(k/2,i)==ht.lfhsh(1,k/2) && hs[j^1].lfhsh(i-k/2+1,k/2)==ht.lfhsh(k/2+1,k/2)); int ans=0; for(i=1;i<=n;++i) for(j=0;j<2;++j){ if(s[j][i]==t[1]) {ans=pls(ans,pls(l[i-1][j][m-1],r[i+1][j][m-1]));if(m==1) ans=mns(ans,1);} for(k=2;k<=m;k+=2){ if(bl[i][j][k]) ans=pls(ans,r[i+1][j^1][m-k]); if(br[i][j][k]) ans=pls(ans,l[i-1][j^1][m-k]); } if(m==2&&bl[i][j][2]) ans=mns(ans,1); } printf("%d\n",ans);}int main(){ int i; scanf("%s",s[0]+1); scanf("%s",s[1]+1); scanf("%s",t+1); n=strlen(s[0]+1); m=strlen(t+1); hs[0].init(s[0],n); hs[1].init(s[1],n); ht.init(t,m); solve(); return 0;}