OJ Board

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

XXXXXX
##X X
XXXXXX
_________

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.

gives: 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 ?

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

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

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

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

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

Regards,
angga888

Your hint is very usefull !!!

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

Best luck

Dominik Michniewski

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

hello.

what should be the output of the following input?
thanx.

The output should be : Good Luck!

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