Четвёртый открытый Зеленоградский турнир 2008

#include <stdio.h>
#include <time.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>


#define MAX_H 128
#define MAX_W 128
#define MAX_C 50
#define BITS 7
#define countof(a) (sizeof(a)/sizeof(a[0]))

int H, W, C;
short _workfld[ MAX_H * MAX_W ];
char cache[1000], *cache_ptr = cache;
#define mul10(a) (((a)<<1) + ((a)<<3))
struct region
{
    short minx; 
    short maxx;
    short maxy;
};


void ReadField()
{
    int i = 0, j = 0;
    char row[ MAX_H * 3 + 1 ];
    scanf("%d%d%d%\n", &H, &W, &C);

    memset( _workfld, 0xff, sizeof( short ) * MAX_H * MAX_W );

    for( i = 1; i <= H; i ++ )
    {
        char *p = row;
        gets( p );

        j = ( i << BITS ) + 1;

        _workfld[j] ++;

        while ( *p )
        {
            if ( *p == ' ' )
            {
                _workfld[ ++j ]++;
                p++;
            }

            _workfld[j] = mul10(_workfld[j]) + *p++-'0';
        }
    }
}
void flush()
{
    *--cache_ptr = 0;
    puts( cache );
    cache_ptr = cache;
}
void put_coords( short x, short y )
{
    short b = y / 10;
    short a = x / 10;

    if ( cache_ptr - cache > 990 )
        flush();

    if ( b ) *cache_ptr++ = b + '0';
    *cache_ptr++ = y - mul10(b) + '0';
    *cache_ptr++ = ' ';
    if ( a ) *cache_ptr++ = a + '0';
    *cache_ptr++ = x - mul10(a) + '0';
    *cache_ptr++ = 10;

}
void LocateRegion( short x, short y, short c, struct region *r )
{
    int i = ( y << BITS ) + x;

    if ( r->minx > x ) r->minx = x;
    if ( r->maxx < x ) r->maxx = x;
    if ( r->maxy < y ) r->maxy = y;

    _workfld[i] = -1;

    if ( _workfld[i+1] == c )
        LocateRegion( x + 1, y, c, r );

    if ( _workfld[i-1] == c )
        LocateRegion( x - 1, y, c, r );

    if ( _workfld[i+MAX_W] == c )
        LocateRegion( x, y + 1, c, r );

    if ( _workfld[i-MAX_W] == c )
        LocateRegion( x, y - 1, c, r );
}
void DropRegion( struct region r )
{
    int x, i, maxi = r.maxy << BITS;
 
    for( x = r.minx; x <= r.maxx; x ++ )
    {
        int d = 0;

        for( i = maxi + x; i > x; i -= MAX_W )
        {
            if ( _workfld[i] < 0 )
                d += MAX_W;
            else if ( d )
            {
                _workfld[i + d] = _workfld[i];
                _workfld[i] = -1;
            }
        }
    }
}

int NextTurn( short bestC, struct region reg)
{
    int x, y, i, found = 0;

    for ( y = 1; y <= reg.maxy; y ++ )
    {
        i = (y << BITS) + reg.minx;

        for ( x = reg.minx; x <= reg.maxx; x ++, i++ )
        {
            int c = _workfld[i];

            if ( c != bestC && c >= 0 && 
                ( _workfld[i+1] == c ||
                _workfld[i-1] == c ||
                _workfld[i+MAX_W] == c))
            {
                struct region reg = { x, x, y };
                LocateRegion( x, y, c, &reg );
                DropRegion( reg );
                put_coords( x-1, y-1 );
                found += 1 + NextTurn( bestC, reg );
            }
        }
    }

    return found;
}

short FindBestColor()
{
    short tmp_count[MAX_C];
    char found[MAX_C];
    short color = 0, 
        max_count = 0;
    int x, y, c, i;

    memset( tmp_count, 0, sizeof( short ) * C );

    for ( x = 1; x <= W; x ++ )
    {
        i = x + MAX_W;
        memset( found, 0, C );

        for ( y = 1; y <= H; y ++, i += MAX_W )
            found[_workfld[i]] ++;

        for( c = 0; c < C; c ++ )
        {
            tmp_count[c] += found[c];

            if ( max_count < tmp_count[c] )
            {
                color = c;
                max_count = tmp_count[c];
            }

            if ( !found[c] )
                tmp_count[c] = 0;
        }
    }

    return color;
}
int main()
{
    int t;
    short bestC;
    scanf("%d", &t );
    
    while( t-- )
    {
        
        ReadField( );
        
        printf( "Y\n" );
        bestC = FindBestColor();
        {
            struct region start_reg = {1, W, H};
            while( NextTurn( bestC, start_reg ) || NextTurn( -1, start_reg ));
        }
        flush();
        printf("-1 -1\n");
    }

    return 0;
}