#include<stdio.h>
#include<stdlib.h>
#define MAX 100
#define initial 1
#define visited 2
int a[MAX][MAX];
//int state[MAX][MAX];
int n;
int value[5];
void set_to_initial(int state[n][n])
{
int i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
state[i][j]=initial;
}
}
void BFS(int k,int i,int j,int state[n][n])
{
state[i][j]=visited;
if(i>0)
if(a[i-1][j]==k&&state[i-1][j]==initial)
BFS(k,i-1,j,state);
if(j>0)
if(a[i][j-1]==k&&state[i][j-1]==initial)
BFS(k,i,j-1,state);
if(j<n-1)
if(a[i][j+1]==k&&state[i][j+1]==initial)
BFS(k,i,j+1,state);
if(i<n-1)
if(a[i+1][j]==k&&state[i+1][j]==initial)
BFS(k,i+1,j,state);
}
void BFS2(int i,int j,int state[n][n])
{
state[i][j]=visited;
if(i>0)
if(a[i-1][j]==0&&state[i-1][j]==initial)
BFS2(i-1,j,state);
else if(a[i-1][j]!=0&&state[i-1][j]==initial)
BFS(a[i-1][j],i-1,j,state);
if(j>0)
if(a[i][j-1]==0&&state[i][j-1]==initial)
BFS2(i,j-1,state);
else if(a[i][j-1]!=0&&state[i][j-1]==initial)
BFS(a[i][j-1],i,j-1,state);
if(j<n-1)
if(a[i][j+1]==0&&state[i][j+1]==initial)
BFS2(i,j+1,state);
else if(a[i][j+1]!=0&&state[i][j+1]==initial)
BFS(a[i][j+1],i,j+1,state);
if(i<n-1)
if(a[i+1][j]==0&&state[i+1][j]==initial)
BFS2(i+1,j,state);
else if(a[i+1][j]!=0&&state[i+1][j]==initial)
BFS(a[i+1][j],i+1,j,state);
}
int countArea(int state[n][n])
{
int i,j,k;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(a[i][j]!=0&&state[i][j]==visited)
for(k=0;k<5;k++)
if(a[i][j]==k+1)
value[k]=value[k]+1;
int x=1;
int max=value[0];
for(i=1;i<5;i++)
{
if(value[i]>=max)
{
max=value[i];
x=i+1;
}
}
for(i=0;i<5;i++)
value[i]=0;
//printf("%d\n",x);
return x;
}
void initialize(int state[n][n])
{
int i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(a[i][j]!=0)
state[i][j]=initial;
}
void setValue(int x,int state[n][n])
{
int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(a[i][j]==0&&state[i][j]==visited)
a[i][j]=x;
}
}
}
main()
{
int T,i,j,k,count,tot,countZero,flag;
for(int t=1;t<=T;t++)
{
count=0;
tot=0;
countZero=0;
flag=0;
if(n<4||n>100)
{
break;
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(a[i][j]<0||a[i][j]>5)
{
flag=1;
break;
}
}
if(flag==1)
break;
}
if(flag==1)
break;
int state[n][n];
set_to_initial(state);
int abcd[n*n];
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(a[i][j]==0&&state[i][j]==initial)
{
BFS2(i,j,state);
countZero++;
abcd[countZero]=countArea(state);
initialize(state);
}
}
}
//printf("%d\n",countZero);
countZero=0;
set_to_initial(state);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(a[i][j]==0&&state[i][j]==initial)
{
BFS(0,i,j,state);
countZero++;
setValue(abcd[countZero],state);
}
}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
}
set_to_initial(state);
for(k=1;k<=n;k++)
{ count=0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(a[i][j]==k&&state[i][j]==initial)
{
BFS(k,i,j,state);
count++;
}
//printf("\n#%d %d\n",k,count);
tot+=count;
}
}
}
I2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8c3RkbGliLmg+CiNkZWZpbmUgTUFYIDEwMAojZGVmaW5lIGluaXRpYWwgMQojZGVmaW5lIHZpc2l0ZWQgMgppbnQgYVtNQVhdW01BWF07Ci8vaW50IHN0YXRlW01BWF1bTUFYXTsKaW50IG47CmludCB2YWx1ZVs1XTsKdm9pZCBzZXRfdG9faW5pdGlhbChpbnQgc3RhdGVbbl1bbl0pCnsKIGludCBpLGo7CiBmb3IoaT0wO2k8bjtpKyspCiBmb3Ioaj0wO2o8bjtqKyspCiB7CiBzdGF0ZVtpXVtqXT1pbml0aWFsOwogfQp9CnZvaWQgQkZTKGludCBrLGludCBpLGludCBqLGludCBzdGF0ZVtuXVtuXSkKewogc3RhdGVbaV1bal09dmlzaXRlZDsKIGlmKGk+MCkKIGlmKGFbaS0xXVtqXT09ayYmc3RhdGVbaS0xXVtqXT09aW5pdGlhbCkKIEJGUyhrLGktMSxqLHN0YXRlKTsKIGlmKGo+MCkKIGlmKGFbaV1bai0xXT09ayYmc3RhdGVbaV1bai0xXT09aW5pdGlhbCkKIEJGUyhrLGksai0xLHN0YXRlKTsKIGlmKGo8bi0xKQogaWYoYVtpXVtqKzFdPT1rJiZzdGF0ZVtpXVtqKzFdPT1pbml0aWFsKQogQkZTKGssaSxqKzEsc3RhdGUpOwogaWYoaTxuLTEpCiBpZihhW2krMV1bal09PWsmJnN0YXRlW2krMV1bal09PWluaXRpYWwpCiBCRlMoayxpKzEsaixzdGF0ZSk7Cn0Kdm9pZCBCRlMyKGludCBpLGludCBqLGludCBzdGF0ZVtuXVtuXSkKewogc3RhdGVbaV1bal09dmlzaXRlZDsKIGlmKGk+MCkKIGlmKGFbaS0xXVtqXT09MCYmc3RhdGVbaS0xXVtqXT09aW5pdGlhbCkKIEJGUzIoaS0xLGosc3RhdGUpOwogZWxzZSBpZihhW2ktMV1bal0hPTAmJnN0YXRlW2ktMV1bal09PWluaXRpYWwpCiBCRlMoYVtpLTFdW2pdLGktMSxqLHN0YXRlKTsKIGlmKGo+MCkKIGlmKGFbaV1bai0xXT09MCYmc3RhdGVbaV1bai0xXT09aW5pdGlhbCkKIEJGUzIoaSxqLTEsc3RhdGUpOwogZWxzZSBpZihhW2ldW2otMV0hPTAmJnN0YXRlW2ldW2otMV09PWluaXRpYWwpCiBCRlMoYVtpXVtqLTFdLGksai0xLHN0YXRlKTsKIGlmKGo8bi0xKQogaWYoYVtpXVtqKzFdPT0wJiZzdGF0ZVtpXVtqKzFdPT1pbml0aWFsKQogQkZTMihpLGorMSxzdGF0ZSk7CiBlbHNlIGlmKGFbaV1baisxXSE9MCYmc3RhdGVbaV1baisxXT09aW5pdGlhbCkKIEJGUyhhW2ldW2orMV0saSxqKzEsc3RhdGUpOwogaWYoaTxuLTEpCiBpZihhW2krMV1bal09PTAmJnN0YXRlW2krMV1bal09PWluaXRpYWwpCiBCRlMyKGkrMSxqLHN0YXRlKTsKIGVsc2UgaWYoYVtpKzFdW2pdIT0wJiZzdGF0ZVtpKzFdW2pdPT1pbml0aWFsKQogQkZTKGFbaSsxXVtqXSxpKzEsaixzdGF0ZSk7Cn0KaW50IGNvdW50QXJlYShpbnQgc3RhdGVbbl1bbl0pCnsKIGludCBpLGosazsKIGZvcihpPTA7aTxuO2krKykKIGZvcihqPTA7ajxuO2orKykKIGlmKGFbaV1bal0hPTAmJnN0YXRlW2ldW2pdPT12aXNpdGVkKQogZm9yKGs9MDtrPDU7aysrKQogaWYoYVtpXVtqXT09aysxKQogdmFsdWVba109dmFsdWVba10rMTsKIGludCB4PTE7CiBpbnQgbWF4PXZhbHVlWzBdOwogZm9yKGk9MTtpPDU7aSsrKQogewogaWYodmFsdWVbaV0+PW1heCkKIHsKIG1heD12YWx1ZVtpXTsKIHg9aSsxOwogfQogfQogZm9yKGk9MDtpPDU7aSsrKQogdmFsdWVbaV09MDsKIC8vcHJpbnRmKCIlZFxuIix4KTsKIHJldHVybiB4Owp9CnZvaWQgaW5pdGlhbGl6ZShpbnQgc3RhdGVbbl1bbl0pCnsKIGludCBpLGo7CiBmb3IoaT0wO2k8bjtpKyspCiBmb3Ioaj0wO2o8bjtqKyspCiBpZihhW2ldW2pdIT0wKQogc3RhdGVbaV1bal09aW5pdGlhbDsKfQp2b2lkIHNldFZhbHVlKGludCB4LGludCBzdGF0ZVtuXVtuXSkKewogaW50IGksajsKIGZvcihpPTA7aTxuO2krKykKIHsKIGZvcihqPTA7ajxuO2orKykKIHsKIGlmKGFbaV1bal09PTAmJnN0YXRlW2ldW2pdPT12aXNpdGVkKQogYVtpXVtqXT14OwogfQogfQp9Cm1haW4oKQp7CiBpbnQgVCxpLGosayxjb3VudCx0b3QsY291bnRaZXJvLGZsYWc7CiBzY2FuZigiJWQiLCZUKTsKIGZvcihpbnQgdD0xO3Q8PVQ7dCsrKQogewogY291bnQ9MDsKIHRvdD0wOwogY291bnRaZXJvPTA7CiBmbGFnPTA7CiBzY2FuZigiJWQiLCZuKTsKIGlmKG48NHx8bj4xMDApCiB7CiBicmVhazsKIH0KIGZvcihpPTA7aTxuO2krKykKIHsKIGZvcihqPTA7ajxuO2orKykKIHsKIHNjYW5mKCIlZCIsJmFbaV1bal0pOwogaWYoYVtpXVtqXTwwfHxhW2ldW2pdPjUpCiB7CiBmbGFnPTE7CiBicmVhazsKIH0KIH0KIGlmKGZsYWc9PTEpCiBicmVhazsKIH0KIGlmKGZsYWc9PTEpCiBicmVhazsKIGludCBzdGF0ZVtuXVtuXTsKIHNldF90b19pbml0aWFsKHN0YXRlKTsKIGludCBhYmNkW24qbl07CiBmb3IoaT0wO2k8bjtpKyspCiB7CiBmb3Ioaj0wO2o8bjtqKyspCiB7CiBpZihhW2ldW2pdPT0wJiZzdGF0ZVtpXVtqXT09aW5pdGlhbCkKIHsKIEJGUzIoaSxqLHN0YXRlKTsKIGNvdW50WmVybysrOwogYWJjZFtjb3VudFplcm9dPWNvdW50QXJlYShzdGF0ZSk7CiBpbml0aWFsaXplKHN0YXRlKTsKIH0KIH0KIH0KIC8vcHJpbnRmKCIlZFxuIixjb3VudFplcm8pOwogY291bnRaZXJvPTA7CiBzZXRfdG9faW5pdGlhbChzdGF0ZSk7CiBmb3IoaT0wO2k8bjtpKyspCiB7CiBmb3Ioaj0wO2o8bjtqKyspCiB7CiBpZihhW2ldW2pdPT0wJiZzdGF0ZVtpXVtqXT09aW5pdGlhbCkKIHsKIEJGUygwLGksaixzdGF0ZSk7CiBjb3VudFplcm8rKzsKIHNldFZhbHVlKGFiY2RbY291bnRaZXJvXSxzdGF0ZSk7CiB9CiB9CiB9CiBmb3IoaT0wO2k8bjtpKyspCiB7CiBmb3Ioaj0wO2o8bjtqKyspCiBwcmludGYoIiVkICIsYVtpXVtqXSk7CiBwcmludGYoIlxuIik7CiB9CiBzZXRfdG9faW5pdGlhbChzdGF0ZSk7CiBmb3Ioaz0xO2s8PW47aysrKQogeyBjb3VudD0wOwogZm9yKGk9MDtpPG47aSsrKQogZm9yKGo9MDtqPG47aisrKQogaWYoYVtpXVtqXT09ayYmc3RhdGVbaV1bal09PWluaXRpYWwpCiB7CiBCRlMoayxpLGosc3RhdGUpOwogY291bnQrKzsKIH0KIC8vcHJpbnRmKCJcbiMlZCAlZFxuIixrLGNvdW50KTsKIHRvdCs9Y291bnQ7CiB9CiBwcmludGYoIiMlZCAlZCIsdCx0b3QpOwogfQp9