1185.txt

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

#include <stdio.h>

int n, m;

int map[100];
int s[100], sn;
int p[100];
int ans[100][100][100];

void fill_s( int k, int h, int sum )
{
    int i;
    
	if( k >= m ){
	    s[sn] = h;
	    p[sn] = sum;
	    sn++;
	    return;
	}
 
 	for( i=k; i<m; i++ ){
      	fill_s( i+3, h|(1<<i), sum+1 );
    }
    
	s[sn] = h;
 	p[sn] = sum;
 	sn++;
}

void init()
{
    int i, j;
    char c[2];
    
    scanf( "%d %d", &n, &m );
    
    for( i=0; i<n; i++ ){
        map[i] = 0;
        for( j=0; j<m; j++ ){
        	scanf( "%1s", c );
         	if( c[0] == 'H' ) map[i] |= (1<<j);
        }
    }
    
    sn = 0;
    fill_s( 0, 0, 0 );
}

void doit()
{
    int i, j, k, t, l, answer;
    
    if( n == 1 ){
        t = 0;
     	for( i=0; i<sn; i++ ){
            if( ( s[i] & map[0] ) == 0 && p[i] > t )
            	t = p[i];
     	}
     	
      	printf( "%d\n", t );
        return; 	
    }
    
	answer = 0;  
  	        	    	
	for( i=0; i<sn; i++ ){
        for( j=0; j<sn; j++ ){
 				if( ( s[i] & map[0] ) == 0 && ( s[j] & map[1] ) == 0 && ( s[i] & s[j] ) == 0 )
       				ans[1][i][j] = p[i] + p[j];
   				else ans[1][i][j] = 0;
   				
   				if( n == 2 && ans[1][i][j] > answer )
            		answer = ans[1][i][j];
   		}
 	}
  	
 	for( l=2; l<n; l++ )
 	for( i=0; i<sn; i++ )
 	for( j=0; j<sn; j++ ){
 	    ans[l][i][j] = 0;
 	    if( ( s[i] & map[l-1] ) == 0 && ( s[j] & map[l] ) == 0 && ( s[i] & s[j] ) == 0 ){
 	        
          	t = 0;
 	        
 	        for( k=0; k<sn; k++ ){
 	            if( ( s[k] & map[l-2] ) == 0 && ( s[k] & s[j] ) == 0 && ans[l-1][k][i] > t )
 	            	t = ans[l-1][k][i];
   			}
      
          	ans[l][i][j] = t + p[j];
           	
            if( l == n-1 && ans[l][i][j] > answer )
            	answer = ans[l][i][j];
     	}
 	}           	
 	            	
  	printf( "%d\n", answer );
}

int main()
{
    init();
    doit();
    return 0;
}