ZOJ 3697 Bad-written Number

dp[ i ][ j ] += dp[ i-1 ][ k ],match(j,k). dp[i][j]는 i가 j일 때의 방안 수를 나타낸다.
DP라기보다는 시뮬레이션 문제다.
첫 번째와 마지막 숫자는 따로 토론하고 중간은 남은 조건에 부합해야 한다.
중간 열과 나머지 두 열의 '|' 는 모두 입력 상태에 부합해야 한다.연결 부분은 '|' 의 합집합을 취하고, 합집합은 입력 상태와 같아야 한다.
첫 번째 숫자는 앞의 두 열이 모두 입력 상태에 부합되고, 마지막 숫자는 뒤의 두 열이 되어야 한다.  
위모는 주간 경기만 되면 여러 가지 못해- -!

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>

#pragma comment(linker, "/STACK:1024000000");
#define EPS (1e-8)
#define LL long long int
#define ULL unsigned long long int
#define _LL __int64
#define _INF 0x3f3f3f3f
#define INF 40000000
#define Mod 1000000007

using namespace std;

char s[3][20010];

int dp[10010][10];

char dig[10][3][4] =
{
    {{' ','_',' ','\0'},{'|',' ','|','\0'},{'|','_','|','\0'}},

    {{' ',' ',' ','\0'},{' ',' ','|','\0'},{' ',' ','|','\0'}},

    {{' ','_',' ','\0'},{' ','_','|','\0'},{'|','_',' ','\0'}},

    {{' ','_',' ','\0'},{' ','_','|','\0'},{' ','_','|','\0'}},

    {{' ',' ',' ','\0'},{'|','_','|','\0'},{' ',' ','|','\0'}},

    {{' ','_',' ','\0'},{'|','_',' ','\0'},{' ','_','|','\0'}},

    {{' ','_',' ','\0'},{'|','_',' ','\0'},{'|','_','|','\0'}},

    {{' ','_',' ','\0'},{' ',' ','|','\0'},{' ',' ','|','\0'}},

    {{' ','_',' ','\0'},{'|','_','|','\0'},{'|','_','|','\0'}},

    {{' ','_',' ','\0'},{'|','_','|','\0'},{' ','_','|','\0'}},
};

bool Match(int w)
{
    int i ,j;

    for(i = 0;i < 3; ++i)
    {
        for(j = 0;j  < 3; ++j)
        {
            if(dig[w][i][j] != s[i][j+1])
                return false;
        }
    }
    return true;
}

bool Match_H(int w)
{
    int i,j;

    for(i = 0;i < 3; ++i)
    {
        for(j = 0;j < 3; ++j)
        {
            if(dig[w][i][j] != s[i][j+1] && (j != 2 || (j == 2 && dig[w][i][j] == '|')))
                return false;
        }
    }

    return true;
}

bool Match_(int len,int v)
{
    int i,j;

    for(i = 0;i < 3; ++i)
    {
        for(j = 0;j < 3; ++j)
        {
            if(dig[v][i][j] != s[i][j+len] && (j != 2 || (j == 2 && dig[v][i][j] == '|')) && (j != 0 || (j == 0 && dig[v][i][j] == '|')) )
                return false;
        }
    }
    return true;
}

bool Match_M(int len,int u,int v)
{
    int i;

    for(i = 0;i < 3; ++i)
    {
        if(dig[u][i][2] != '|' && dig[v][i][0] != '|' && s[i][len] == '|')
            return false;
        if(dig[u][i][2] != ' ' && dig[v][i][0] != ' ' && s[i][len] == ' ')
            return false;
    }

    return true;
}

bool Match_E(int len,int u,int v)
{
    int i,j;

    for(i = 0;i < 3; ++i)
    {
        if(dig[u][i][2] != '|' && dig[v][i][0] != '|' && s[i][len] == '|')
            return false;
        if(dig[u][i][2] != ' ' && dig[v][i][0] != ' ' && s[i][len] == ' ')
            return false;
    }

    for(i = 0;i < 3; ++i)
    {
        for(j = 0;j < 3; ++j)
        {
            if(dig[v][i][j] != s[i][j+len] && (j != 0 || (j == 0 && dig[v][i][j] == '|')) )
                return false;
        }
    }

    return true;
}

void solve(int n)
{
    int i,j,k,l;

    if(n == 1)
    {
        for(i = 0;i <= 9; ++i)
        {
            if(Match(i))
                break;
        }
        if(i == 10)
        {
            printf("0
");
        }
        else
        {
            printf("1
");
        }
        return ;
    }

    for(i = 0;i <= n; ++i)
    {
        memset(dp[i],0,sizeof(dp[i]));
    }

    for(i = 0;i <= 9; ++i)
    {
        if(Match_H(i))
            dp[1][i] = 1;
        else
            dp[1][i] = 0;
    }

    int Top = 2*n+1 - 2;

    int a,b;

    for(i = 3;i < Top; i += 2)
    {
        a = i/2 + 1;
        b = a - 1;

        for(j = 0;j <= 9; ++j)
        {
            if(Match_(i,j))
            {

                for(k = 0;k <= 9; ++k)
                {
                    if(dp[b][k] && Match_M(i,k,j))
                    {
                        dp[a][j] += dp[b][k];
                        dp[a][j] %= Mod;
                    }
                }
            }
        }

        for(l = 0;l <= 9; ++l)
        {
            if(dp[a][l])
                break;
        }

        if(l == 10)
        {
            printf("0
");
            return ;
        }

    }

    a = i/2+1;
    b = a-1;

    for(i = 0;i <= 9; ++i)
    {
        for(j = 0;j <= 9; ++j)
        {
            if(dp[b][j] && Match_E(Top,j,i))
            {
                dp[a][i] += dp[b][j];
                dp[a][i] %= Mod;
            }
        }
    }

    int ans = 0;

    for(i = 0;i <= 9; ++i)
    {
        ans += dp[n][i];
        ans %= Mod;
    }

    printf("%d
",ans);

    return ;
}

int main()
{
    int i,T,n;

    scanf("%d",&T);

    while(T--)
    {
        scanf("%d%*c",&n);

        for(i = 0; i < 3; ++i)
        {
            gets(s[i]+1);
        }

        solve(n);
    }
    return 0;
}