| ||||
|
На главную
.............. Задачи .............. Финальная статистика .............. Общая статистика .............. Правила .............. 
|
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define nul(a) memset(a,0,sizeof(a))
int cnts[50];
char use[100][100];
int a[100][100];
struct pos
{
int i,v;
void init(int _i,int _v)
{
i=_i;
v=_v;
}
bool operator<(pos p) const
{
return v<p.v;
}
} p[50];
int _p[50],n,m;
char mn[100];
int s[10000][2];
int down[100];
void init(int u,int i,int j)
{
s[u][0]=i;
s[u][1]=j;
}
int fil(int i,int j)
{
int u=1,c=a[i][j],d;
init(0,i,j);
use[i][j]=1;
for (d=0;d<u;d++)
{
i=s[d][0];
j=s[d][1];
if (i&&!use[i-1][j]&&a[i-1][j]==c)
{
init(u++,i-1,j);
use[i-1][j]=1;
}
if (i+1<n&&!use[i+1][j]&&a[i+1][j]==c)
{
init(u++,i+1,j);
use[i+1][j]=1;
}
if (j&&!use[i][j-1]&&a[i][j-1]==c)
{
init(u++,i,j-1);
use[i][j-1]=1;
}
if (j+1<m&&!use[i][j+1]&&a[i][j+1]==c)
{
init(u++,i,j+1);
use[i][j+1]=1;
}
}
return u;
}
void del(int i,int j)
{
int u=1,c=a[i][j],d,z;
init(0,i,j);
a[i][j]=-1;
nul(mn);
for (d=0;d<u;d++)
{
i=s[d][0];
j=s[d][1];
if (mn[j]<i)
mn[j]=i;
if (i&&a[i-1][j]==c)
{
init(u++,i-1,j);
a[i-1][j]=-1;
}
if (i+1<n&&a[i+1][j]==c)
{
init(u++,i+1,j);
a[i+1][j]=-1;
}
if (j&&a[i][j-1]==c)
{
init(u++,i,j-1);
a[i][j-1]=-1;
}
if (j+1<m&&a[i][j+1]==c)
{
init(u++,i,j+1);
a[i][j+1]=-1;
}
}
for (j=0;j<m;j++)
{
for (z=i=mn[j];i>=down[j];i--)
if (a[i][j]+1)
a[z--][j]=a[i][j];
for (;z>=down[j];z--)
a[z][j]=-1;
}
for (d=0;d<u;d++)
down[s[d][1]]++;
}
int main()
{
#ifdef pperm
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int ti,tests,c,i,j,k,mn,mi,mj,cur;
scanf("%d",&tests);
for (ti=0;ti<tests;ti++)
{
nul(down);
nul(cnts);
printf("Y\n");
scanf("%d%d%d",&n,&m,&c);
for (i=0;i<n;i++)
for (j=0;j<m;j++)
{
scanf("%d",&a[i][j]);
cnts[a[i][j]]++;
}
for (i=0;i<c;i++)
p[i].init(i,cnts[i]);
/*for (i=0;i<c-1;i++)
for (j=0;j<c-i-1;j++)
if (cnts[p[j]]>cnts[p[j+1]])
{
p[j]^=p[j+1];
p[j+1]^=p[j];
p[j]^=p[j+1];
}*/
sort(p,p+c);
for (i=0;i<c;i++)
_p[p[i].i]=i;
for (i=0;i<n;i++)
for (j=0;j<m;j++)
a[i][j]=_p[a[i][j]];
if (c==4)
{
nul(use);
mn=1;
for (k=0;k<c-4;)
{
up4: mn=0;
for (j=0;j<m;j++)
for (i=down[j];i<n;i++)
if (a[i][j]+1&&a[i][j]<=k)
{
if (fil(i,j)>1)
{
del(i,j);
printf("%d %d\n",i,j);
nul(use);
mn=1;
}
}
if (!mn)
k++;
}
k=c-5;
mn=12345;
for (j=0;j<m;j++)
for (i=down[j];i<n;i++)
if (!use[i][j]&&a[i][j]==c-4)
{
cur=fil(i,j);
if (cur>1&&cur<mn)
{
mi=i;
mj=j;
mn=cur;
}
}
if (mn!=12345)
{
del(mi,mj);
printf("%d %d\n",mi,mj);
nul(use);
goto up4;
}
for (j=0;j<m;j++)
for (i=down[j];i<n;i++)
if (!use[i][j]&&a[i][j]==c-3)
{
cur=fil(i,j);
if (cur>1&&cur<mn)
{
mi=i;
mj=j;
mn=cur;
}
}
if (mn!=12345)
{
del(mi,mj);
printf("%d %d\n",mi,mj);
nul(use);
goto up4;
}
for (j=0;j<m;j++)
for (i=down[j];i<n;i++)
if (!use[i][j]&&a[i][j]==c-2)
{
cur=fil(i,j);
if (cur>1&&cur<mn)
{
mi=i;
mj=j;
mn=cur;
}
}
if (mn!=12345)
{
del(mi,mj);
printf("%d %d\n",mi,mj);
nul(use);
goto up4;
}
for (j=0;j<m;j++)
for (i=down[j];i<n;i++)
if (!use[i][j]&&a[i][j]==c-1)
{
cur=fil(i,j);
if (cur>1&&cur<mn)
{
mi=i;
mj=j;
mn=cur;
}
}
if (mn!=12345)
{
del(mi,mj);
printf("%d %d\n",mi,mj);
nul(use);
goto up4;
}
printf("-1 -1\n");
}
else
if (c<=5||(p[c-1].v+p[c-2].v+p[c-3].v)*5>=n*m*2)
{
nul(use);
mn=1;
for (k=0;k<c-3;)
{
up3: mn=0;
for (j=0;j<m;j++)
for (i=down[j];i<n;i++)
if (a[i][j]+1&&a[i][j]<=k)
{
if (fil(i,j)>1)
{
del(i,j);
printf("%d %d\n",i,j);
nul(use);
mn=1;
}
}
if (!mn)
k++;
}
k=c-4;
mn=12345;
for (j=0;j<m;j++)
for (i=down[j];i<n;i++)
if (!use[i][j]&&a[i][j]==c-3)
{
cur=fil(i,j);
if (cur>1&&cur<mn)
{
mi=i;
mj=j;
mn=cur;
}
}
if (mn!=12345)
{
del(mi,mj);
printf("%d %d\n",mi,mj);
nul(use);
goto up3;
}
for (j=0;j<m;j++)
for (i=down[j];i<n;i++)
if (!use[i][j]&&a[i][j]==c-2)
{
cur=fil(i,j);
if (cur>1&&cur<mn)
{
mi=i;
mj=j;
mn=cur;
}
}
if (mn!=12345)
{
del(mi,mj);
printf("%d %d\n",mi,mj);
nul(use);
goto up3;
}
for (j=0;j<m;j++)
for (i=down[j];i<n;i++)
if (!use[i][j]&&a[i][j]==c-1)
{
cur=fil(i,j);
if (cur>1&&cur<mn)
{
mi=i;
mj=j;
mn=cur;
}
}
if (mn!=12345)
{
del(mi,mj);
printf("%d %d\n",mi,mj);
nul(use);
goto up3;
}
printf("-1 -1\n");
}
else
if ((p[c-1].v+p[c-2].v)*7>=n*m*2)
{
nul(use);
mn=1;
for (k=0;k<c-2;)
{
up2: mn=0;
for (j=0;j<m;j++)
for (i=down[j];i<n;i++)
if (a[i][j]+1&&a[i][j]<=k)
{
if (fil(i,j)>1)
{
del(i,j);
printf("%d %d\n",i,j);
nul(use);
mn=1;
}
}
if (!mn)
k++;
}
k=c-3;
mn=12345;
for (j=0;j<m;j++)
for (i=down[j];i<n;i++)
if (!use[i][j]&&a[i][j]==c-2)
{
cur=fil(i,j);
if (cur>1&&cur<mn)
{
mi=i;
mj=j;
mn=cur;
}
}
if (mn==12345)
mn=0;
if (mn)
{
del(mi,mj);
printf("%d %d\n",mi,mj);
nul(use);
goto up2;
}
mn=12345;
for (j=0;j<m;j++)
for (i=down[j];i<n;i++)
if (!use[i][j]&&a[i][j]==c-1)
{
cur=fil(i,j);
if (cur>1&&cur<mn)
{
mi=i;
mj=j;
mn=cur;
}
}
if (mn==12345)
mn=0;
if (mn)
{
del(mi,mj);
printf("%d %d\n",mi,mj);
nul(use);
goto up2;
}
printf("-1 -1\n");
}
else
{
nul(use);
for (k=0;k<c-1;)
{
up: mn=0;
for (j=0;j<m;j++)
for (i=down[j];i<n;i++)
if (a[i][j]+1&&a[i][j]<=k)
{
if (fil(i,j)>1)
{
del(i,j);
printf("%d %d\n",i,j);
nul(use);
mn=1;
}
}
if (!mn)
k++;
}
mn=12345;
for (j=0;j<m;j++)
for (i=down[j];i<n;i++)
if (!use[i][j]&&a[i][j]==c-1)
{
cur=fil(i,j);
if (cur>1&&cur<mn)
{
mi=i;
mj=j;
mn=cur;
}
}
if (mn!=12345)
{
del(mi,mj);
printf("%d %d\n",mi,mj);
nul(use);
k=c-2;
goto up;
}
printf("-1 -1\n");
}
}
return 0;
}
|
|||
| ||||