Poj Solution 3043

http://poj.org/problem?id=3043

#include <stdio.h>


#define max(a,b) ((a)>(b)?(a):(b))

int clac( char *w, int len, char map[32][32], int n, int m ) {
    int s[5][1000], sn[5] = {0};
    int ans[5][1000] = { 0 }, i, j, k, ii, l, sum = 0;
    for( i=0; i<n; i++ )
    for( j=0; j<m; j++ )
    for( k=0; k<len; k++ )
        if( map[i][j] == w[k] )
            s[k][sn[k]++] = (i<<5)|j;

    for( i=0; i<sn[0]; i++ )
        ans[0][i] = 1;
    for( i=0; i<len-1; i++ ) {
        ii = i+1;
        k = 0;
        for( j=0; j<sn[i] && k<sn[ii]; j++ ) 
        if( ans[i][j] ){
            while( k<sn[ii] && s[ii][k]<=s[i][j] )
                k++;
            for( l=k; l<sn[ii]; l++ ) {
                if( ( s[ii][l] & 31 ) >= ( s[i][j] & 31 ) )
                    ans[ii][l] += ans[i][j];
            }
        }
    }
    
    for( i=0; i<sn[len-1]; i++ )
        sum += ans[len-1][i];
    return sum;
}
        
int main( ) {
    char map[32][32], w[10];
    int count[256] = { 0 };
    int n, m, i, ans = 0, j;

    scanf( "%d%d", &n, &m );
    for( i=n-1; i>=0; i-- ) {
        scanf( "%s", map[i] );
        for( j=0; j<m; j++ )
            count[map[i][j]]++;
    }

    while( scanf( "%s", w ) == 1 ) {
        for( i=0; w[i]; i++ )
            if( count[ w[i] ] == 0 )
                break;
        if( w[i] == 0 )
            ans += clac( w, i, map, n, m );
    }
    printf( "%dn", ans );
    return 0;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *