UVa 910

simple dp problem again
state:
    dp[i][j] - how many ways to reach point j with i steps
transition:
    dp[i][j]+=dp[i-1][k], 1<=k<=26
    do this on both when p[k][0]==j and when p[k][1]==j

/* UVas */
/*****************************************************************************/
char t0, t1, tx;
int n, m;
int p[27][3];
int d[31][27];
int main(void) {
    while (cin>>n) {
        for (int i=1; i<=n; i++) {
            cin>>t0>>t0>>t1>>tx;
            p[i][0]=t0-'@';
            p[i][1]=t1-'@';
            p[i][2]=tx=='x'?1:0;
        }
        cin>>m;
        memset(d, 0, sizeof(d));
        d[0][1]=1;
        for (int i=1; i<=m; i++) {
            for (int j=1; j<=n; j++) {
                for (int k=1; k<=n; k++) {
                    if (p[k][0]==j) {
                        d[i][j]+=d[i-1][k];
                    }
                    if (p[k][1]==j) {
                        d[i][j]+=d[i-1][k];
                    }
                }
            }
        }
        int r=0;
        for (int i=1; i<=n; i++) {
            r+=d[m][i]*p[i][2];
        }
        cout<<r<<endl;
    }
    return 0;
}
/*****************************************************************************/