[HDU5965]扫雷

题目大意：

一个\(3\times n(n\le10000)\)的扫雷，第\(2\)排没有雷。告诉你第\(2\)排上的数，问有几种埋雷的方案？

思路：

动态规划。

将\(1,3\)两排的雷全部往左移一格，即第\(2\)排上第\(i\)列的数只和\(1,3\)两排第\(i-2,i-1,i\)列的雷有关。

\(f[i][j][k]\)表示前\(i\)列，第\(i\)列有\(k\)个雷，第\(i-1\)列有\(j\)个雷的方案数。

转移十分显然。

时间复杂度\(\mathcal O(n)\)。

源代码：

#include
    
     #include
     
      #include
      
       inline int getint() {    register char ch;    while(!isdigit(ch=getchar()));    register int x=ch^'0';    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');    return x;}const int N=10001,mod=1e8+7;char s[N+1];int f[N][3][3];int main() {    for(register int T=getint();T;T--) {        memset(f,0,sizeof f);        scanf("%s",&s[1]);        const int n=strlen(&s[1]);        for(register int i=1;i<=n;i++) s[i]-='0';        f[0][0][0]=1;        if(s[1]>=1) f[0][0][1]=2;        if(s[1]>=2) f[0][0][2]=1;        for(register int i=1;i<=n;i++) {            for(register int j=0;j<3;j++) {                for(register int k=0;k<3;k++) {                    if(f[i-1][j][k]==0||j+k>s[i]||s[i]>2+j+k) continue;                    (f[i][k][s[i]-j-k]+=f[i-1][j][k])%=mod;                    if(s[i]-j-k==1) (f[i][k][1]+=f[i-1][j][k])%=mod;                }            }        }        int ans=0;        for(register int i=0;i<3;i++) {            (ans+=f[n][i][0])%=mod;        }        printf("%d\n",ans);    }    return 0;}