782 - Contour Painting

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

Kamp
New poster
Posts: 18
Joined: Tue Mar 05, 2002 2:00 am
Location: Poland (3-city)
Contact:

782 - Contour Painting

Post by Kamp » Thu Mar 28, 2002 7:48 pm

I've question... what will be the answer to this case ?
_________
XXXXXX
* X X
XXXXXX
_________

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Thu Mar 28, 2002 10:46 pm

XXXXXX
##X X
XXXXXX
_________

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum » Sun May 19, 2002 10:56 pm

my program gives the exact output for the given samples and with no extra spaces on the ends of lines.
anyone got any better test cases as i am getting wa here and i really dont know why.

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

What about this?

Post by junjieliang » Mon May 20, 2002 3:11 pm

Code: Select all

______________
    XXXXXXXX
         XXXX   *
  XXXXXXXXX
______________

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum » Mon May 20, 2002 6:34 pm

gives:

Code: Select all

__________
    XXXXXXXX#
         XXXX#
  XXXXXXXXX##
______________
but then the problem does state:
Each contour is placed on its grid in such a way that it is fully surrounded by free grid points (spaces).
If this hadnt been explicitly stated then I would do something for this case. Are you saying the problem description is wrong ?

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

Post by LittleJohn » Fri Oct 04, 2002 8:24 pm

I don't think there will be such a case because my two different AC programs give different outputs for this input.

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

782 - Countour Painting

Post by Dominik Michniewski » Tue Feb 11, 2003 3:32 pm

Could anyone tell me what I'm doing wrong ?
I'll be very greatful for help ....

I use following algorithm:

1. Read grid until readed line not start with "_"
2. Find position of asterisk (ax,ay) in this grid
3. Find border character B - first character which is different from set {*,<space>,_}
4. Fill area of grid starting with position of asterisk (bordered by B)
5. Set points (x,y) to '#' where from any side of this point exists border

Is this algorithm wrong ? What should I change in it ?

Best regards
Dominik
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

782 Contour Painting -- WA

Post by angga888 » Sun Feb 23, 2003 1:17 pm

Help me, I'm getting WA and WA again on this problem. Please someone help me to give the output for these cases.

Code: Select all

4

  XXXXXXXXXXXX
  X           X
  X           X         X
  X           X
  X   XXXXX   X
  X   X       X
  X   X *
  X   X       X
  X   XXXXX   X
  X           X
  X           X        X
  X           X
  XXXXXXXXXXXX

__________

  XXX
  X X   *
  X

__________

   *
__________

  XXXXXXXXXX
  X        X
  X XXXXXX X
  X X *  X X
  XXXXXXXXXX

__________

And please give me another tricky cases. Thanks very much.

Regards,
angga888

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Sun Feb 23, 2003 4:59 pm

At first, I also used algorithm just exactly like yours, but I got WA for several times. After I changed the algorithm, finally I got Accepted.
This is my algorithm :
1. Read grid until a line start with "_"
2. Find the position of asterisk.
3. I do not use one variable to store the border character. So any printable char except {*,space,_,#} can be border. My program can handle this input :

Code: Select all

XKHDKJS
J  *  D
JLNLKJN
__________
P.S: I don't know if that's a valid input or not, but it's better if you can handle it.
4. Use floodfill starting from position of asterisk. If row-1 or row+1 or col-1 or col+1 is a border, then change that position to "#".

That's all I did, hope you can get it Accepted soon.
Good Luck ! :D

Best regards,
angga888

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Sun Feb 23, 2003 5:03 pm

I got Accepted now. :D
Thanks to everyone who tries to help me.

Regards,
angga888

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

Post by Dominik Michniewski » Tue Feb 25, 2003 10:05 am

Your hint is very usefull !!!

I got Accepted now. I change only part which check border ...

Best luck

Dominik Michniewski
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

raysa
New poster
Posts: 40
Joined: Wed Dec 18, 2002 4:23 pm
Location: Indonesia

Post by raysa » Sun Mar 16, 2003 4:01 pm

Give up!
I'm on it for WEEKS 'n 0.253 sec WA is my best... :evil:
What's wrong:
[cpp]#include <stdio.h>
#include <string.h>

bool value[35][85],star;
int i,j,x,max,lenx,posrow,poscol;
char str[35][85],*col;

void explore(int posrow,int poscol)
{
if (posrow-1>=1 && str[posrow-1][poscol]==' ')
{
if (value[posrow-2][poscol]==true || value[posrow][poscol]==true || value[posrow-1][poscol-1]==true || value[posrow-1][poscol+1]==true) str[posrow-1][poscol]='#';
else str[posrow-1][poscol]=1;
explore(posrow-1,poscol);
}
if (posrow+1<x && str[posrow+1][poscol]==' ')
{
if (value[posrow][poscol]==true || value[posrow+2][poscol]==true || value[posrow+1][poscol-1]==true || value[posrow+1][poscol+1]==true) str[posrow+1][poscol]='#';
else str[posrow+1][poscol]=1;
explore(posrow+1,poscol);
}
if (poscol-1>=0 && str[posrow][poscol-1]==' ')
{
if (value[posrow-1][poscol-1]==true || value[posrow+1][poscol-1]==true || value[posrow][poscol-2]==true || value[posrow][poscol]==true) str[posrow][poscol-1]='#';
else str[posrow][poscol-1]=1;
explore(posrow,poscol-1);
}
if (poscol+1<=80 && str[posrow][poscol+1]==' ')
{
if (value[posrow-1][poscol+1]==true || value[posrow+1][poscol+1]==true || value[posrow][poscol]==true || value[posrow][poscol+2]==true) str[posrow][poscol+1]='#';
else str[posrow][poscol+1]=1;
explore(posrow,poscol+1);
}
}

void main ()
{
scanf ("%d%c",&x,&str[-1][0]);
x=1; max=0;
while (gets(str[x]))
{
lenx=strlen(str[x]);
if (lenx>max && str[x][0]!='_') max=lenx;
for (i=0;i<lenx;i++)
{
if (str[x]!=' ' && str[x]!='_' && str[x]!='*') value[x]=true;
}
col=strchr(str[x],'*');
if (col)
{
star=true; posrow=x; poscol=col-str[x];
if (value[posrow-1][poscol]==true || value[posrow+1][poscol]==true || value[posrow][poscol-1]==true || value[posrow][poscol+1]==true) str[posrow][poscol]='#';
else str[posrow][poscol]=' ';
}
if (str[x][0]=='_')
{
for (i=1;i<x;i++)
{
for (j=max+1;j>=0;j--)
{
if (str[j]!='\0') break;
else str[j]=' ';
}
}
if(star==true) explore(posrow,poscol);
/*for (i=1;i<x;i++)
{
for (j=max+1;j>=0;j--)
{
if (str[j]!=1 && str[j]!=' ') break;
else str[j]='\0';
}
}*/
for (i=1;i<x;i++)
{
for (j=0;j<=max+1;j++)
{
if (str[j]!=1) printf ("%c",str[i][j]);
else printf (" ");
if (str[i][j]=='\0') break;
}
printf("\n");
}
printf ("%s\n",str[x]);
for (i=1;i<x;i++)
{
for (j=0;j<=max+1;j++)
{
value[i][j]=false;
}
memset(str[i],'\0',max+2);
}
memset(str[x],'\0',max+2);
x=1; max=0; star=false;
}
else x++;
}
}[/cpp]

Thx,
Raysa
Last edited by raysa on Thu Mar 20, 2003 4:19 pm, edited 1 time in total.

Adil
Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:

Post by Adil » Sun Mar 16, 2003 9:48 pm

hello.

what should be the output of the following input?

Code: Select all

1
XXXXXXXXXXXXX
X       X  *
XXXXXXXXXXXXXXX
____
thanx.

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Tue Mar 18, 2003 3:29 pm

The output should be :

Code: Select all

XXXXXXXXXXXXX# 
X       X######   
XXXXXXXXXXXXXXX# 
____ 
Good Luck! :D

User avatar
saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Location: Dhaka, Bangladesh
Contact:

Post by saiqbal » Wed Mar 19, 2003 5:30 pm

your output seems a bit weird to me, coz u've printed some
spaces after the end of second line. r u sure there will be
spaces? :-?

Code: Select all

XXXXXXXXXXXXX#
X       X######@@@
XXXXXXXXXXXXXXX#
____
you've printed 3 extra spaces at the place where i put '@'.

im actually screwed. getting WA :(

thanx
-sohel

Post Reply

Return to “Volume 7 (700-799)”