Hdu OJ 5965 扫雷（递推）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5965

题目大意：中文题，自己读

解图思路：对于每一列都有三种情况--0， 1， 2。 如果第一列确定地雷的数量， 那么下一列地雷的数量为已知的， 同理可以求出剩下所有列地雷的数量。需要注意， 对于1的情况， 有0，1和1，0两种， 所以需要乘以2

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N = 10003, mod = 1e8+7;

char str[N];
int dp[N], num[N];

void solve()
{
    scanf("%s", str);
    for(int i=0; str[i]; ++ i)
        num[i+1] = str[i] - '0';

    int len = strlen(str);
    memset(dp, 0, sizeof(dp));

    int ans = 0;
    for(int i=0; i<=num[1] && i<3; ++ i)
    {
        dp[1] = i;
        bool is = true;
        for(int j=2; j<=len; ++ j)
        {
            dp[j] = num[j-1] - dp[j-1] - dp[j-2];
            if(dp[j] > 2 || dp[j] < 0)
            {
                is = false;
                break;
            }
        }
        if(is == false)
            continue;
        if(dp[len] + dp[len-1] != num[len])
            continue;

        int res = 1;
        for(int j=1; j<=len; ++ j)
        {
            if(dp[j] == 1)
                res = (res * 2) % mod;
        }
        ans = (ans + res) % mod;
    }
    printf("%d
", ans);
}
int main()
{
    int t;
    scanf("%d", &t);
    for(int i=1; i<=t; ++ i)
        solve();
    return 0;
}