Poj Solution 1867

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

#include <stdio.h>
#include <vector>
#include <string.h>
using namespace std;

#define YES     { printf( "samen" );         continue; }
#define NO        { printf( "differentn" );    continue; }
#define PT(a)     (printf("an"));

struct node
{
    vector< node* > next;
    char c;

}mem[500];

char w[1000];
int u;

node* new_node()
{
    mem[u++].next.clear();
    return &mem[u-1];
} 

int creat( int a, node *p )
{
    node *q;
    p->c = w[a];
    a++;
    if( w[a] == '(' )
    {
        a++;
        while( 1 )//w[a] != '' )
        {
            if( w[a] == ',' ) a++;
        
            q = new_node();
            p -> next.push_back( q );
            q -> next.push_back( p );
            a = creat( a, q );

            if( w[a] == ')' )
            {
                a++;
                return a;
            }
        }
    }
    return a;
}

    
bool judge( node *p1, node *f1, node *p2, node *f2 )
{
    int d1 = p1->next.size(), d2 = p2->next.size(), i, j, k;

    if( d1 != d2 || p1->c != p2->c ) return false;    

    for( i = 0; i < d1; i++ )
        if( p1->next[i] == f1 ) break;

    for( j = 0; j < d2; j++ )
        if( p2->next[j] == f2 ) break;

    for( k = 1; k < d1; k++ )
        if( ! judge( p1->next[(i+k)%d1], p1, p2->next[(j+k)%d2], p2 ) )
            return false;

    return true;
}

int main()
{
    bool key;
    int cas, i, j, h;


    scanf( "%d", &cas );

    while( cas-- )
    {

        u=0;

        scanf( "%s", w );
        mem[u].next.clear();
        u++;
        creat( 0, &mem[u-1] );
        
        h = u;

        scanf( "%s", w );
        mem[u].next.clear();
        u++;
        creat( 0, &mem[u-1] );
        
        if( u == 2 ) 
        {
            if( mem[0].c == mem[1].c )    YES
            else NO
        }

        if( h*2 != u )
            NO

        for( i=0; i < h; i++ )
        if( mem[i].next.size() == 1 )
            break;

        if( i < h )
        {
            for( key=1, j=h; j < u && key ; j++ )
            if( mem[j].next.size() == 1 && mem[j].c == mem[i].c )
            {
                if( judge( mem[i].next[0], &mem[i], mem[j].next[0], &mem[j] ) )
                {
                    key = 0;
                }
            }

            if( !key ) YES
        }
        
        NO
    }
    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 *