| ||||
|
На главную
.............. Задачи .............. Финальная статистика .............. Общая статистика .............. Правила .............. 
|
#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;
}
|
|||
| ||||