| ||||
|
На главную
.............. Задачи .............. Финальная статистика .............. Общая статистика .............. Правила .............. 
|
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#ifndef ONLINE_JUDGE
#include <time.h>
#include <assert.h>
#endif
typedef unsigned char U8;
typedef unsigned int U32;
typedef unsigned long long U64;
typedef signed char I8;
typedef signed int I32;
typedef signed long long I64;
struct game
{
I32 _h, _w, _ncolors;
U8 _board[0x80*0x80];
//#ifndef ONLINE_JUDGE
I32 _dscope, _scope;
//#endif
I32 _colors[50];
I32 _heights[0x100];
U8 _tabu_color;
U8 _ay[100];
} g;
#define at(x,y) ((g._board+0x81)[(y)*128+(x)])
int input(FILE* fin)
{
char sz[4096];
I32 x,y,c;
//#ifndef ONLINE_JUDGE
g._scope = 0;
g._dscope = 0;
//#endif
memset(g._colors, 0, sizeof(g._colors));
do
fgets(sz, 4096, fin);
while(sz[0]==0 || sz[1]==0);
sscanf(sz,"%d %d %d", &g._h, &g._w, &g._ncolors);
#ifndef ONLINE_JUDGE
assert(4<=g._w && g._w<=100);
assert(4<=g._h && g._h<=100);
assert(3<=g._ncolors && g._ncolors<=50);
#endif
if(/*g._ncolors<=4 ||*/ g._ncolors>8 || g._w!=g._h || g._w<22)
{
for(x=0; x<g._h; x++)
{
do
fgets(sz, 4096, fin);
while(sz[0]==0 || sz[1]==0);
}
return 0;
} else
{
I32 most_color = 0;
g._tabu_color = 0xFF;
memset(g._board, 0xCC, sizeof(g._board));
for(x=0; x<g._h; x++)
{
char*p=sz;
do
fgets(sz, 4096, fin);
while(sz[0]==0 || sz[1]==0);
for(y=0; y<g._w; y++)
{
c = strtol(p, &p, 10);
#ifndef ONLINE_JUDGE
assert(0<=c && c<g._ncolors);
#endif
at(x,y) = (U8)(c);
g._colors[c] ++;
}
}
for(c=0; c<g._ncolors; c++)
{
if( g._colors[c]>most_color )
{
most_color = g._colors[c];
g._tabu_color=c;
}
}
#if 0
most_color = 0;
for(U8 c=0; c<g._ncolors; c++)
{
if( c!=g._tabu_color && g._colors[c]>most_color )
{
most_color = _colors[c];
g._tabu_color2=c;
}
}
#endif
for(y=0; y<g._w; y++)
{
g._heights[y] = 0;
}
return 1;
}
}
//#ifndef ONLINE_JUDGE
I32
//#else
//void
//#endif
shot_assume(I32 x, I32 y, U8 c)
{
U32 lenobject = 1;
at(x, y) = 0xFF; // visited, !=c
g._heights[y] ++;
g._ay[y]=1;
//#ifndef ONLINE_JUDGE
if( at(x-1,y)==c ) lenobject += shot_assume(x-1,y,c);
if( at(x,y-1)==c ) lenobject += shot_assume(x,y-1,c);
if( at(x+1,y)==c ) lenobject += shot_assume(x+1,y,c);
if( at(x,y+1)==c ) lenobject += shot_assume(x,y+1,c);
return lenobject;
//#else
// if( at(x-1,y)==c ) shot_assume(x-1,y,c);
// if( at(x,y-1)==c ) shot_assume(x,y-1,c);
// if( at(x+1,y)==c ) shot_assume(x+1,y,c);
// if( at(x,y+1)==c ) shot_assume(x,y+1,c);
//#endif
}
#define detonable(x, y, c) ((at(x+1,y)==c)||(at(x,y+1)==c))
#define detonablex(x, y, c) ((at(x+1,y)==c))
#define detonabley(x, y, c) ((at(x,y+1)==c))
void solve(char*p, int mode)
{
p+=sprintf(p,"Y\n");
while(1)
{
I32 x,y;
U8 c;
//#ifndef ONLINE_JUDGE
I32 len;
//#endif
#if 1
if(g._tabu_color != 0xFF )
{
#define c2 at(x-1,y)
#define c4 at(x-1,y+1)
#define c5 at(x,y-1)
#define c6 at(x,y+2)
#define c1 at(x+1,y)
#define c3 at(x+1,y+1)
if(mode==1)
for(y=0; y<g._w; y++)
{
for(x=g._heights[y]; x<g._h-1; x++)
{
c=at(x, y);
//if( c!=g._tabu_color && detonabley(x,y,c) && (c1==c2 || c3==c4 ) )
if( c!=g._tabu_color && detonabley(x,y,c) && (c1==c2 || c3==g._tabu_color && c3==c4) )
//if( c!=g._tabu_color && detonabley(x,y,c) && (c1==g._tabu_color && c3==g._tabu_color) )
{
goto _shot;
}
}
}
#if 0
if(mode==0) // a bit better but slower
for(y=0; y<g._w; y++)
{
for(x=g._heights[y]; x<g._h-1; x++)
{
c=at(x, y);
//if( c!=g._tabu_color && detonabley(x,y,c) && (c1==c2 || c2==c5 ) )
if( c!=g._tabu_color && detonabley(x,y,c) && (c1==c2 && c1==g._tabu_color) )
{
goto _shot;
}
}
}
#endif
#if 0
if(mode==1)
for(y=0; y<g._w; y++)
{
for(x=g._heights[y]; x<g._h-1; x++)
{
c=at(x, y);
if( c!=g._tabu_color && detonabley(x,y,c) && (c1==c2 /*|| c2==c5*/ || c3==c4 ) )
//if( c!=g._tabu_color && detonabley(x,y,c) && (c1==c2 || c3==g._tabu_color && c3==c4) )
//if( c!=g._tabu_color && detonabley(x,y,c) && (c1==g._tabu_color && c3==g._tabu_color) )
{
goto _shot;
}
}
}
#endif
#if 1
for(y=0; y<g._w; y++)
{
for(x=g._heights[y]; x<g._h-1; x++)
{
c=at(x, y);
if(c!=g._tabu_color && detonabley(x,y,c) )
{
goto _shot;
}
}
}
#endif
for(y=0; y<g._w; y++)
{
for(x=g._heights[y]; x<g._h-1; x++)
{
c=at(x, y);
if( c!=g._tabu_color && detonablex(x,y,c) )
{
goto _shot;
}
}
}
#if 1
x = g._h-1;
for(y=0; y<g._w; y++)
{
//for(x=0; x<g._h; x++)
{
c=at(x, y);
if(c!=0xFF && c!=g._tabu_color && detonabley(x,y,c) )
{
goto _shot;
}
}
}
#endif
g._tabu_color = 0xFF;
}
#endif
for(y=0; y<g._w; y++)
{
for(x=g._heights[y]; x<g._h; x++)
{
c=at(x, y);
if( detonable(x,y,c) )
{
goto _shot;
}
}
}
break;
_shot:
p+=sprintf(p,"%d %d\n", x, y);
memset(g._ay,0,g._w);
//#ifndef ONLINE_JUDGE
len =
//#endif
shot_assume(x, y, c);
// derecha
for(y=0; y<g._w; y++)
{
if(g._ay[y])
{
I32 xfrom = g._h-1;
for(x=xfrom; x>=0; x--)
{
while(xfrom>=0 && at(xfrom,y)==0xFF)
xfrom--;
at(x,y) = xfrom>=0 ? at(xfrom,y) : 0xFF;
xfrom--;
}
}
}
//#ifndef ONLINE_JUDGE
g._dscope = len*(len-1);
g._scope += g._dscope;
//#endif
}
p+=sprintf(p,"-1 -1");
}
char sol0[2000000], sol1[2000000], sol2[2000000];
int main(int argc, char** argv)
{
#ifndef ONLINE_JUDGE
I32 total=0;
#endif
I32 ncases,cas;
char sz[100];
#ifndef ONLINE_JUDGE
I32 h1=0,h2=0,h3=0,h0=0;
I32 pr1=0,pr2=0,pr3=0,pr0=0;
#endif
#ifndef ONLINE_JUDGE
char name[256];
#ifdef _WIN32
strcpy(name, strrchr(argv[0],'\\')+1);
#else
strcpy(name, strrchr(argv[0],'/')+1);
#endif
{char*p=strrchr(name,'.'); if(p)strcpy(p+1, "txt"); else strcat(name,".txt");}
freopen(name,"r",stdin);
#ifdef _WIN32
freopen("nul","w",stdout);
#else
freopen("/dev/null","w",stdout);
#endif
#endif
fgets(sz, 100, stdin);
sscanf(sz,"%d", &ncases);
for(cas=0; cas<ncases; cas++)
{
int binput = input(stdin);
if(!binput)
{
printf("N\n");
} else
{
I32 scope1=0,scope2=0,scope0=0;
//if(g._ncolors<4)
//{
// solve(sol1,1); scope1 = g._scope;
// puts(sol1);
//} else
{
struct game gbak = g;
solve(sol0,0); scope0 = g._scope;
g = gbak; solve(sol1,1); scope1 = g._scope;
// g = gbak; solve(sol2,2); scope2 = g._scope;
// g = gbak; solve(sol3,3); scope3 = g._scope;
// if(scope3>scope2 && scope3>scope1 && scope3>scope0)
// {
// h3++;
// puts(sol3);
// } else
/*if(scope2>scope0 && scope2>scope1)
{
#ifndef ONLINE_JUDGE
h2++;
pr2+=scope2-max(scope0,scope1);
#endif
puts(sol2);
} else*/ if(scope1>scope0)
{
#ifndef ONLINE_JUDGE
h1++;
pr1+=scope1-max(scope2,scope0);
#endif
puts(sol1);
} else
{
#ifndef ONLINE_JUDGE
h0++;
pr0+=scope0-max(scope2,scope1);
#endif
puts(sol0);
}
}
#ifndef ONLINE_JUDGE
total += max(max(scope0, scope1), max(scope2,0));
fprintf(stderr,"SCOPE: %-10d %-10d %-10d %-10d\n", scope0, scope1, scope2, 0);
#endif
}
}
#ifndef ONLINE_JUDGE
fprintf(stderr,"TOTAL: %d\n", total);
fprintf(stderr," VOTE: %-10d %-10d %-10d %-10d\n", h0, h1, h2, h3);
fprintf(stderr," PR: %-10d %-10d %-10d %-10d\n", pr0, pr1, pr2, pr3);
#endif
return 0;
}
|
|||
| ||||