### 782 - Contour Painting

Posted:

**Thu Mar 28, 2002 7:48 pm**I've question... what will be the answer to this case ?

_________

XXXXXX

* X X

XXXXXX

_________

_________

XXXXXX

* X X

XXXXXX

_________

Page **1** of **4**

Posted: **Thu Mar 28, 2002 7:48 pm**

I've question... what will be the answer to this case ?

_________

XXXXXX

* X X

XXXXXX

_________

_________

XXXXXX

* X X

XXXXXX

_________

Posted: **Thu Mar 28, 2002 10:46 pm**

XXXXXX

##X X

XXXXXX

_________

##X X

XXXXXX

_________

Posted: **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.

anyone got any better test cases as i am getting wa here and i really dont know why.

Posted: **Mon May 20, 2002 3:11 pm**

Code: Select all

```
______________
XXXXXXXX
XXXX *
XXXXXXXXX
______________
```

Posted: **Mon May 20, 2002 6:34 pm**

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).

Posted: **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.

Posted: **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

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

Posted: **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.

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

Posted: **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 :
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 !

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 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 !

Best regards,

angga888

Posted: **Sun Feb 23, 2003 5:03 pm**

I got Accepted now.

Thanks to everyone who tries to help me.

Regards,

angga888

Thanks to everyone who tries to help me.

Regards,

angga888

Posted: **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

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

Best luck

Dominik Michniewski

Posted: **Sun Mar 16, 2003 4:01 pm**

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 (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

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 (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]

}

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

else str

}

}

if(star==true) explore(posrow,poscol);

/*for (i=1;i<x;i++)

{

for (j=max+1;j>=0;j--)

{

if (str

else str

}

}*/

for (i=1;i<x;i++)

{

for (j=0;j<=max+1;j++)

{

if (str

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

Posted: **Sun Mar 16, 2003 9:48 pm**

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
____
```

Posted: **Tue Mar 18, 2003 3:29 pm**

The output should be :
Good Luck!

Code: Select all

```
XXXXXXXXXXXXX#
X X######
XXXXXXXXXXXXXXX#
____
```

Posted: **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?
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