782  Contour Painting
Moderator: Board moderators
782  Contour Painting
I've question... what will be the answer to this case ?
_________
XXXXXX
* X X
XXXXXX
_________
_________
XXXXXX
* X X
XXXXXX
_________

 Experienced poster
 Posts: 169
 Joined: Wed Oct 31, 2001 2:00 am
 Location: Singapore
What about this?
Code: Select all
______________
XXXXXXXX
XXXX *
XXXXXXXXX
______________
gives:
but then the problem does state:
Code: Select all
__________
XXXXXXXX#
XXXX#
XXXXXXXXX##
______________
If this hadnt been explicitly stated then I would do something for this case. Are you saying the problem description is wrong ?Each contour is placed on its grid in such a way that it is fully surrounded by free grid points (spaces).

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

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
782  Countour Painting
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
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)
Born from ashes  restarting counter of problems (800+ solved problems)
782 Contour Painting  WA
Help me, I'm getting WA and WA again on this problem. Please someone help me to give the output for these cases.
And please give me another tricky cases. Thanks very much.
Regards,
angga888
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
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 :
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 row1 or row+1 or col1 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 !
Best regards,
angga888
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
__________
4. Use floodfill starting from position of asterisk. If row1 or row+1 or col1 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 !
Best regards,
angga888

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
Your hint is very usefull !!!
I got Accepted now. I change only part which check border ...
Best luck
Dominik Michniewski
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)
Born from ashes  restarting counter of problems (800+ solved problems)
Give up!
I'm on it for WEEKS 'n 0.253 sec WA is my best...
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 (posrow1>=1 && str[posrow1][poscol]==' ')
{
if (value[posrow2][poscol]==true  value[posrow][poscol]==true  value[posrow1][poscol1]==true  value[posrow1][poscol+1]==true) str[posrow1][poscol]='#';
else str[posrow1][poscol]=1;
explore(posrow1,poscol);
}
if (posrow+1<x && str[posrow+1][poscol]==' ')
{
if (value[posrow][poscol]==true  value[posrow+2][poscol]==true  value[posrow+1][poscol1]==true  value[posrow+1][poscol+1]==true) str[posrow+1][poscol]='#';
else str[posrow+1][poscol]=1;
explore(posrow+1,poscol);
}
if (poscol1>=0 && str[posrow][poscol1]==' ')
{
if (value[posrow1][poscol1]==true  value[posrow+1][poscol1]==true  value[posrow][poscol2]==true  value[posrow][poscol]==true) str[posrow][poscol1]='#';
else str[posrow][poscol1]=1;
explore(posrow,poscol1);
}
if (poscol+1<=80 && str[posrow][poscol+1]==' ')
{
if (value[posrow1][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=colstr[x];
if (value[posrow1][poscol]==true  value[posrow+1][poscol]==true  value[posrow][poscol1]==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
I'm on it for WEEKS 'n 0.253 sec WA is my best...
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 (posrow1>=1 && str[posrow1][poscol]==' ')
{
if (value[posrow2][poscol]==true  value[posrow][poscol]==true  value[posrow1][poscol1]==true  value[posrow1][poscol+1]==true) str[posrow1][poscol]='#';
else str[posrow1][poscol]=1;
explore(posrow1,poscol);
}
if (posrow+1<x && str[posrow+1][poscol]==' ')
{
if (value[posrow][poscol]==true  value[posrow+2][poscol]==true  value[posrow+1][poscol1]==true  value[posrow+1][poscol+1]==true) str[posrow+1][poscol]='#';
else str[posrow+1][poscol]=1;
explore(posrow+1,poscol);
}
if (poscol1>=0 && str[posrow][poscol1]==' ')
{
if (value[posrow1][poscol1]==true  value[posrow+1][poscol1]==true  value[posrow][poscol2]==true  value[posrow][poscol]==true) str[posrow][poscol1]='#';
else str[posrow][poscol1]=1;
explore(posrow,poscol1);
}
if (poscol+1<=80 && str[posrow][poscol+1]==' ')
{
if (value[posrow1][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=colstr[x];
if (value[posrow1][poscol]==true  value[posrow+1][poscol]==true  value[posrow][poscol1]==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.

 Learning poster
 Posts: 57
 Joined: Sun Sep 29, 2002 12:00 pm
 Location: in front of the monitor :)
 Contact:
hello.
what should be the output of the following input?
thanx.
what should be the output of the following input?
Code: Select all
1
XXXXXXXXXXXXX
X X *
XXXXXXXXXXXXXXX
____
The output should be :
Good Luck!
Code: Select all
XXXXXXXXXXXXX#
X X######
XXXXXXXXXXXXXXX#
____
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?
you've printed 3 extra spaces at the place where i put '@'.
im actually screwed. getting WA
thanx
sohel
spaces after the end of second line. r u sure there will be
spaces?
Code: Select all
XXXXXXXXXXXXX#
X X######@@@
XXXXXXXXXXXXXXX#
____
im actually screwed. getting WA
thanx
sohel