## 776 - Monkeys in a Regular Forest

All about problems in Volume VII. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

### 776 - Monkeys in a Regular Forest

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)
Subeen
Experienced poster

Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh

### 776

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 36 6 7 3 3 3 38 7 9 7 7 7 7`

My output:
Code: Select all
`1 2 3 4 5 5 36 6 7 3 3 3 38 7 4 7 7 7 7`
Dominik Michniewski
Guru

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

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

Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

Thx Xenon ....
I hope that this is my problem ...
Dominik Michniewski
Guru

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

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

Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

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

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

Dominik Michniewski wrote: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.
Ivan Golubev
Experienced poster

Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

### accepted, at last

Finaly got AC. Hint: think of BIG forests...
xenon
Learning poster

Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

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

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

### At last ...

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
Dominik Michniewski
Guru

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

### 776

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]
htl
Experienced poster

Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

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

Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK

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

Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

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?
htl
Experienced poster

Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

and what about the 100 ? is that the max too ?
Caesum
Experienced poster

Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK

Next

Return to Volume VII

### Who is online

Users browsing this forum: No registered users and 1 guest