776 - Monkeys in a Regular Forest

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

Moderator: Board moderators

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

776 - Monkeys in a Regular Forest

Post by 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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

776

Post by 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
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

Post by xenon »

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

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski »

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

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

Post by xenon »

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

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski »

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

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

Post by Ivan Golubev »

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.

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

accepted, at last

Post by xenon »

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

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski »

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

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

At last ...

Post by 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 :-D

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

776

Post by 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
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum »

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

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

Post by htl »

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

Post by 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
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum »

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

Post Reply

Return to “Volume 7 (700-799)”