776 - Monkeys in a Regular Forest

[Subeen]

i tried to solve the prob. using dfs. but got W.A. can u pls help me?

Code: Select all

removed

(problem is in taking input)

[Dominik Michniewski]

Could anybody say me why sample input for case 1 has '9' in row three ? I think that in this place could be '4' ...
I got WA many times and I have no idea what tricks have this problem ...

From sample output:

Code: Select all

1 2 3 4 5 5 3
6 6 7 3 3 3 3
8 7 9 7 7 7 7

My output:

Code: Select all

1 2 3 4 5 5 3
6 6 7 3 3 3 3
8 7 4 7 7 7 7

[xenon]

The two trees 'E' are not neighboring, so they will be occupied by different families.

[Dominik Michniewski]

Thx Xenon ....
I hope that this is my problem ...

[xenon]

I don't know. It looks like a simple problem, but all I get are WAs.

[Dominik Michniewski]

I think, that this problem can be judge to WA if PE occur.... like "Rotating Sentences (4xx)" ....

[Ivan Golubev]

I think, that this problem can be judge to WA if PE occur.... like "Rotating Sentences (4xx)" ....

No, I've got PE and my solution (because I'm really lazy ) doesn't contains any formatting functions -- just outputs numbers with single space between them.

[xenon]

Finaly got AC. Hint: think of BIG forests...

[Dominik Michniewski]

I use from alwys list of list
and BIG forest isn't problem

[Dominik Michniewski]

Finally got Accepted, but PE ....
I made a solution like problem simple output, also I don't know why PE occur .... maybe after last test I don't have to print newline character ?
thx Xenon & Ivan for help

[htl]

Does the code have any bug? I solved the problem like this one all got acceptd..
[c]
#include<stdio.h>
#include<string.h>
#define YES 1
#define NO 0
int table[100][100],row,maxcol,species;
char monkey[100][100];
void s(int,int);
void output(void);
void main(void)
{
int x,y,exit,len;
char buffer[300];
while(1)
{
row=maxcol=0;
exit=YES;
while(fgets(buffer,300,stdin)!=NULL)
{
len=strlen(buffer)-1;
buffer[len]='\0';
if(len==1 && buffer[0]=='%')
{
exit=NO;
break;
}
for(x=0,y=0;buffer[x]!='\0';x++)
if(buffer[x]>='a' && buffer[x]<='z' || buffer[x]>='A' && buffer[x]<='Z')
monkey[row][y++]=buffer[x];
if(y>maxcol)
maxcol=y;
row++;
}
for(x=0;x<row;x++)
for(y=0;y<maxcol;y++)
table[x][y]=0;
species=0;
for(x=0;x<row;x++)
for(y=0;y<maxcol;y++)
if(!table[x][y])
{
species++;
table[x][y]=species;
s(x,y);
}
output();
if(exit)
break;
}
}
void s(int x,int y)
{
if(x-1>=0 && x-1<row && y-1>=0 && y-1<maxcol && monkey[x-1][y-1]==monkey[x][y] && !table[x-1][y-1])
{
table[x-1][y-1]=species;
s(x-1,y-1);
}
if(x-1>=0 && x-1<row && y>=0 && y<maxcol && monkey[x-1][y]==monkey[x][y] && !table[x-1][y])
{
table[x-1][y]=species;
s(x-1,y);
}
if(x-1>=0 && x-1<row && y+1>=0 && y+1<maxcol && monkey[x-1][y+1]==monkey[x][y] && !table[x-1][y+1])
{
table[x-1][y+1]=species;
s(x-1,y+1);
}
if(x>=0 && x<row && y-1>=0 && y-1<maxcol && monkey[x][y-1]==monkey[x][y] && !table[x][y-1])
{
table[x][y-1]=species;
s(x,y-1);
}
if(x>=0 && x<row && y+1>=0 && y+1<maxcol && monkey[x][y+1]==monkey[x][y] && !table[x][y+1])
{
table[x][y+1]=species;
s(x,y+1);
}
if(x+1>=0 && x+1<row && y-1>=0 && y-1<maxcol && monkey[x+1][y-1]==monkey[x][y] && !table[x+1][y-1])
{
table[x+1][y-1]=species;
s(x+1,y-1);
}
if(x+1>=0 && x+1<row && y>=0 && y<maxcol && monkey[x+1][y]==monkey[x][y] && !table[x+1][y])
{
table[x+1][y]=species;
s(x+1,y);
}
if(x+1>=0 && x+1<row && y+1>=0 && y+1<maxcol && monkey[x+1][y+1]==monkey[x][y] && !table[x+1][y+1])
{
table[x+1][y+1]=species;
s(x+1,y+1);
}
}
void output(void)
{
int x,y,t,max,column[100];
for(y=0;y<maxcol;y++)
{
for(x=0,max=0;x<row;x++)
{
if(table[x][y]<10)
t=1;
else
t=2;
if(t>max)
max=t;
}
column[y]=max;
}
for(x=0;x<row;x++)
{
for(y=0;y<maxcol;y++)
if(y==0)
printf("%*d",column[y],table[x][y]);
else
printf(" %*d",column[y],table[x][y]);
printf("\n");
}
printf("%%\n");
}
[/c]

[Caesum]

you have placed some arbitrary small bounds on things, like printing, etc

[htl]

You mean maybe the species > 100 and I only set the column[] as 1 or 2?

[htl]

This is my new code. It still get WA.
[c]
#include<stdio.h>
#include<string.h>
#define YES 1
#define NO 0
int table[100][100],row,maxcol,species;
char monkey[100][100];
void s(int,int);
void output(void);
void main(void)
{
int x,y,exit,len;
char buffer[300];
while(1)
{
row=maxcol=0;
exit=YES;
while(fgets(buffer,300,stdin)!=NULL)
{
len=strlen(buffer)-1;
buffer[len]='\0';
if(len==1 && buffer[0]=='%')
{
exit=NO;
break;
}
for(x=0,y=0;buffer[x]!='\0';x++)
if(buffer[x]>='a' && buffer[x]<='z' || buffer[x]>='A' && buffer[x]<='Z')
monkey[row][y++]=buffer[x];
if(y>maxcol)
maxcol=y;
row++;
}
for(x=0;x<row;x++)
for(y=0;y<maxcol;y++)
table[x][y]=0;
species=0;
for(x=0;x<row;x++)
for(y=0;y<maxcol;y++)
if(!table[x][y])
{
species++;
table[x][y]=species;
s(x,y);
}
output();
if(exit)
break;
}
}
void s(int x,int y)
{
if(x-1>=0 && x-1<row && y-1>=0 && y-1<maxcol && monkey[x-1][y-1]==monkey[x][y] && !table[x-1][y-1])
{
table[x-1][y-1]=species;
s(x-1,y-1);
}
if(x-1>=0 && x-1<row && y>=0 && y<maxcol && monkey[x-1][y]==monkey[x][y] && !table[x-1][y])
{
table[x-1][y]=species;
s(x-1,y);
}
if(x-1>=0 && x-1<row && y+1>=0 && y+1<maxcol && monkey[x-1][y+1]==monkey[x][y] && !table[x-1][y+1])
{
table[x-1][y+1]=species;
s(x-1,y+1);
}
if(x>=0 && x<row && y-1>=0 && y-1<maxcol && monkey[x][y-1]==monkey[x][y] && !table[x][y-1])
{
table[x][y-1]=species;
s(x,y-1);
}
if(x>=0 && x<row && y+1>=0 && y+1<maxcol && monkey[x][y+1]==monkey[x][y] && !table[x][y+1])
{
table[x][y+1]=species;
s(x,y+1);
}
if(x+1>=0 && x+1<row && y-1>=0 && y-1<maxcol && monkey[x+1][y-1]==monkey[x][y] && !table[x+1][y-1])
{
table[x+1][y-1]=species;
s(x+1,y-1);
}
if(x+1>=0 && x+1<row && y>=0 && y<maxcol && monkey[x+1][y]==monkey[x][y] && !table[x+1][y])
{
table[x+1][y]=species;
s(x+1,y);
}
if(x+1>=0 && x+1<row && y+1>=0 && y+1<maxcol && monkey[x+1][y+1]==monkey[x][y] && !table[x+1][y+1])
{
table[x+1][y+1]=species;
s(x+1,y+1);
}
}
void output(void)
{
int x,y,t,max,column[100];
for(y=0;y<maxcol;y++)
{
for(x=0,max=0;x<row;x++)
{
if(table[x][y]<10)
t=1;
else if(table[x][y]>=10 && table[x][y]<100)
t=2;
else if(table[x][y]>=100 && table[x][y]<1000)
t=3;
else if(table[x][y]>=1000 && table[x][y]<10000)
t=4;
else if(table[x][y]>=10000 && table[x][y]<=32767)
t=5;
if(t>max)
max=t;
}
column[y]=max;
}
for(x=0;x<row;x++)
{
for(y=0;y<maxcol;y++)
if(y==0)
printf("%*d",column[y],table[x][y]);
else
printf(" %*d",column[y],table[x][y]);
printf("\n");
}
printf("%%\n");
}
[/c]

I have a question: will the chars except alphabets appear?

[Caesum]

and what about the 100 ? is that the max too ?