Poj Solution 2185

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

#include <stdio.h>


char map[10000][80];
int n,m;
bool sign[75][10000];

int main()
{
    int i, j, n, m, k, h, l;
    bool key;

    scanf( "%d %d", &n, &m );
    
    for( i=0; i<n; i++ )
    scanf( "%s", map[i] );

    for( k=1; k<m; k++ )
    {
        key = true;
        for( i=0; i<n&&key; i++ )
        for( j=k; j<m; j++ )
        if( map[i][j] != map[i][j%k] )
        {
            key = false;
            break;
        }
        if( key )break;
    }

    for( h=1; h<n; h++ )
    {
        key = true;
        for( j=0; j<m&&key; j++ )
        if( !sign[j][h] )
        {
            for( i=h; i<n; i++ )
            if( map[i][j] != map[i%h][j] )
            {
                key = false;
                break;
            }
            if( key )
            {
                for( l=1; l*h < n; l++ )
                sign[j][l*h] = true;
            }
        }
        if( key )break;
    }

    printf( "%dn", k*h );

    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 *