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

#include <stdio.h>
#include <memory.h>

//#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#define CalcScore
#endif

int n, m, c, L, R, D, left[105], right[105], le;
int Count[55], C;
int mark[105][105], a[105][105], t;

#ifdef CalcScore
#define pl 0

int b[105][105], ans[10005][2], l, mark2[105][105];

void out(char *mes, int b[105][105])
{
   int i, j;
   printf("%s\n", mes);
   for (i=m+pl; i>=1-pl; i--)
   {
      for (j=1-pl; j<=n+pl; j++)
         printf("%2d ", b[j][i]);
      printf("\n");
   }
}

int dfs2(int b[105][105], int mark2[105][105], int x, int y, int c)
{
   int t=b[y][x], res=1;
   mark2[y][x]=c;
   if (mark2[y][x-1]!=c && b[y][x-1]==t)
      res+=dfs2(b, mark2, x-1, y, c);
   if (mark2[y][x+1]!=c && b[y][x+1]==t)
      res+=dfs2(b, mark2, x+1, y, c);
   if (mark2[y-1][x]!=c && b[y-1][x]==t)
      res+=dfs2(b, mark2, x, y-1, c);
   if (mark2[y+1][x]!=c && b[y+1][x]==t)
      res+=dfs2(b, mark2, x, y+1, c);
   return res;
} 

int kill(int x, int y)
{
   int t, i, j, k;
   memset(mark2, 0, sizeof(mark2));
   if (b[y][x]==-1 || (t=dfs2(b, mark2, x, y, 1))==1) return 0;
   for (i=0; i<=m+1; i++)
      b[0][i]=b[n+1][i]=-1;
   for (j=1; j<=n; j++)
   {
      b[j][0]=-1;
      for (i=k=1; b[j][i]!=-1; i++)
         if (!mark2[j][i])
            b[j][k++]=b[j][i];
      while (k<=m+1)
         b[j][k++]=-1;
   }
   return t*(t-1);
}
#endif

void dfs(int x, int y)
{
   mark[y][x]=C;
   if (mark[y][x-1]!=C && a[y][x-1]==t)
   {
      if (x<=D) D=x-1;
      dfs(x-1, y);
   }
   if (mark[y][x+1]!=C && a[y][x+1]==t)
      dfs(x+1, y);
   if (mark[y-1][x]!=C && a[y-1][x]==t)
   {
      if (y<=L) L=y-1;
      dfs(x, y-1);
   }
   if (mark[y+1][x]!=C && a[y+1][x]==t)
   {
      if (y>=R) R=y+1;
      dfs(x, y+1);
   }
}

char buf[35000];
char s[300], *T;

void solve(void)
{
   int i, j, i1, j1, k, q, M, cc;
   memset(Count, 0, sizeof(Count));
   for (i=m; i>=1; i--)
      for (j=1; j<=n; j++)
         Count[a[j][i]]++;
   C=1;
   for (cc=i=0; i<c; i++)
      if (Count[i]>Count[cc]) cc=i;
   memset(mark, 0, sizeof(mark));
   #ifdef CalcScore
   memcpy(b, a, sizeof(b));
   l=0;
   #endif
   M=m;
   le=1;
      for (i=1; i<=M; i++)
         left[i]=1, right[i]=n;
      for (i=M; i>=1; i--)
      {
         for (j=left[i]; j<=right[i]; j++, C++)
            if ((t=a[j][i])!=-1 && t!=cc)
            {
               L=R=j, D=i;
               if (a[j+1][i]!=t && a[j][i-1]!=t && a[j-1][i]!=t && a[j][i+1]!=t) continue;
               dfs(i, j);
               q=0;
               for (i1=k=D; (t=a[L][i1])!=-1; i1++)
               {
                  if (t==a[L-1][i1]) q--;
                  if (mark[L][i1]!=C)
                     if (a[L-1][k++]==t) q++;
               }
               for (i1=k=D; (t=a[R][i1])!=-1; i1++)
               {
                  if (t==a[R+1][i1]) q--;
                  if (mark[R][i1]!=C)
                     if (a[R+1][k++]==t) q++;
               }
               if (q<-3) continue;
               #ifdef CalcScore
               ans[l][0]=i;
               ans[l][1]=j;
               l++;
               #else
                  t=m-i;
                  if (t>=10) *T=t/10+'0', T++, *T=t%10+'0', T++, *T=' ', T++;
                  else *T=t+'0', T++, *T=' ', T++;
                  t=j-1;
                  if (t>=10) *T=t/10+'0', T++, *T=t%10+'0', T++, *T='\n', T++;
                  else *T=t+'0', T++, *T='\n', T++;
               #endif
               for (j1=L; j1<=R; j1++)
               {
                  i1=D;
                  while (mark[j1][i1]!=C) i1++;
                  for (k=i1; (t=a[j1][i1])!=-1; i1++)
                     if (mark[j1][i1]!=C)
                     {
                        a[j1][k]=t;
                        if (k>i)
                        {
                           if (j1<left[k]) left[k]=j1;
                           if (j1>right[k]) right[k]=j1;
                        }
                        k++;
                     }
                  while (k<i1)
                     a[j1][k++]=-1;
               }
               i=M-1, j=left[i]-1;
            }
         right[i]=0, left[i]=n+1;
         while (1)
         {
            while (le<=n && a[le][M]==-1) le++;
            if (le>n) M--, le=1;
            else break;
         }
         if (i>M) i=M+1;
      }
      for (i=1; i<=M; i++)
         left[i]=1, right[i]=n;
      for (i=M; i>=1; i--)
      {
         for (j=left[i]; j<=right[i]; j++, C++)
            if ((t=a[j][i])!=-1)
            {
               L=R=j, D=i;
               if (a[j+1][i]!=t && a[j][i-1]!=t && a[j-1][i]!=t && a[j][i+1]!=t) continue;
               dfs(i, j);
               #ifdef CalcScore
               ans[l][0]=i;
               ans[l][1]=j;
               l++;
               #else
                  t=m-i;
                  if (t>=10) *T=t/10+'0', T++, *T=t%10+'0', T++, *T=' ', T++;
                  else *T=t+'0', T++, *T=' ', T++;
                  t=j-1;
                  if (t>=10) *T=t/10+'0', T++, *T=t%10+'0', T++, *T='\n', T++;
                  else *T=t+'0', T++, *T='\n', T++;
               #endif
               for (j1=L; j1<=R; j1++)
               {
                  i1=D;
                  while (mark[j1][i1]!=C) i1++;
                  for (k=i1; (t=a[j1][i1])!=-1; i1++)
                     if (mark[j1][i1]!=C)
                     {
                        a[j1][k]=t;
                        if (k>i)
                        {
                           if (j1<left[k]) left[k]=j1;
                           if (j1>right[k]) right[k]=j1;
                        }
                        k++;
                     }
                  while (k<i1)
                     a[j1][k++]=-1;
               }
            }
         right[i]=0, left[i]=n+1;
         while (1)
         {
            while (le<=n && a[le][M]==-1) le++;
            if (le>n) M--, le=1;
            else break;
         }
         if (i>M) i=M+1;
      }
}

int main(void)
{
   int i, j, tn, nt, t;
   #ifndef ONLINE_JUDGE
   freopen("ZJAWB.in", "r", stdin);
   freopen("ZJAWB.out", "w", stdout);
   #endif
   scanf("%d", &nt);
   buf[0]='Y';
   buf[1]='\n';
   for (tn=0; tn<nt; tn++)
   {
      scanf("%d%d%d\n", &m, &n, &c);
      for (i=m; i; i--)
      {
         gets(s);
         T=s;
         for (j=1; j<=n; j++)
         {
            if (*(T+1)>='0') a[j][i]=((*T)-'0')*10+T[1]-'0', T+=3;
            else a[j][i]=(*T)-'0', T+=2;
         }
      }
      for (i=0; i<=n+1; i++)
         a[i][0]=a[i][m+1]=-1;
      for (i=1; i<=m; i++)
         a[0][i]=a[n+1][i]=-1;

      T=buf+2;
      solve();
      *T=0;
      printf("%s", buf);
      #ifdef CalcScore
      j=0;
      for (i=0; i<l; i++)
      {
         t=kill(ans[i][0],ans[i][1]);if (t==0) printf("ERROR\n");j+=t;
//         printf("%d", j);out("", b);
      }
      printf("%d -1 -1\n", j);
      #else
      puts("-1 -1");
      #endif
   }

   return 0;
}