3043.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Source

Problem Id:3043  User Id:fzk 
Memory:80K  Time:154MS
Language:G++  Result:Accepted

Source 

#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( "%d\n", ans );
	return 0;
}