782 - Contour Painting

[Kamp]

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

[..]

XXXXXX
##X X
XXXXXX
_________

[Caesum]

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]

Code: Select all

______________
    XXXXXXXX
         XXXX   *
  XXXXXXXXX
______________

[Caesum]

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]

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

[Dominik Michniewski]

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

[angga888]

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

[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 :

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 !

Best regards,
angga888

[angga888]

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

Regards,
angga888

[Dominik Michniewski]

Your hint is very usefull !!!

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

Best luck

Dominik Michniewski

[raysa]

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

[Adil]

hello.

what should be the output of the following input?

Code: Select all

1
XXXXXXXXXXXXX
X       X  *
XXXXXXXXXXXXXXX
____

thanx.

[angga888]

The output should be :

Code: Select all

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

Good Luck!

[saiqbal]

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