10452 - Marcus

[amd-RS]

Is there something special about this problem ? I think it's not difficult, and besides there is only one path, right ?? But I don't know why I get TLE !!!

Thanks for any reply !!!

[Larry]

if you get TLE on this problem, you probably have a problem with how you deal with input.. a loop isn't terminating or something.

[timrau]

This is my code. I can't find out why it doesn't work. Could anyone help me?
[c]#include <stdio.h>
int main(void)
{
int task; /* How many cases */
int m,n; /* m as rows and n as columns */
int fromy,toy; /*as the original problem says, the start point is in the last row and the end point is in the first row, and I consider X axis as vertical and Y axis as horizonal */
int nowx,nowy;
int ta,tb,tc;
char graph[8][8];
const char path[]="IEHOVA#"; /* the sequence for searching */
scanf("%d",&task);
for(ta=1;ta<=task;ta++)
{
scanf("%d%d",&m,&n);
nowx=m-1;
for(tb=0;tb<m;tb++)
scanf("%s",graph[tb]);
for(tb=0;tb<n;tb++)
{
if(graph[m-1][tb]=='@')
nowy=fromy=tb;
if(graph[0][tb]=='#')
toy=tb;
}
for(tb=0;tb<8;tb++)
{
if(tb)
putchar(' ');
if(nowx>0 && graph[nowx-1][nowy]==path[tb])
{
nowx--;
printf("forth");
}
else if(nowy<n-1 && graph[nowx][nowy+1]==path[tb])
{
nowy++;
printf("right");
}
else
{
nowy--;
printf("left");
}
}
putchar('\n');
}
return(0);
}[/c]

[amd-RS]

Are you getting WA ??? I've tried your code and for the input:

Code: Select all

PST#T
BTJAS
TYCVM
YEHOF
XIBKU
N@RJB

it gives me:

Code: Select all

forth forth right right forth forth forth left

instead of:

Code: Select all

forth forth right right forth forth forth

My problem is worst, I'm getting TLE, don't know why !!!

[Larry]

const char path[]="IEHOVA#";

This is 7 characters, from 0 to 6, but:

for(tb=0;tb<8;tb++)

Goes from 0 to 7.

amd-RS: post your IO code, maybe we can help that way...

[timrau]

Thank you all, and my code really get accepted after change this:

for(tb=0;tb<8;tb++)

into this:

for(tb=0;tb<7;tb++)

[amd-RS]

Here is my code:

[c]#include <stdio.h>
#include <string.h>

int main()
{
int cases,m,n,i,j,mcopy,flag_right,flag_left;
char cobble[100000][10];

scanf("%d",&cases);
while(cases)
{

scanf("%d %d",&m,&n);
for(i=0;i<=m;i++)
cobble[0] = '\0';
mcopy = m;
while(mcopy)
{
scanf("%s",cobble[mcopy]);
mcopy--;
}
i=1;
for(j=0;j<=n;j++)
if(strchr("@",cobble[j])!=NULL)
{
break;
}
flag_left=flag_right=0;
while(cobble[j]!='#')
{
if(cobble[i+1][j]=='#')
{
printf("forth ");
i++;
}
else if(cobble[j+1]=='#')
{
printf("right");j++;
}
else if(cobble[j-1]=='#')
{
printf("left");j--;
}
else if(strchr("IEHOVA",cobble[i+1][j])!=NULL)
{
printf("forth ");flag_left=flag_right=0;
i++;
}

else if(strchr("IEHOVA",cobble[j+1])!=NULL && flag_right==0)
{
printf("right ");
flag_left=1;
j++;
}

else if(strchr("IEHOVA",cobble[j-1])!=NULL && flag_left==0)
{
printf("left ");flag_right=0;
j--;
}

}
printf("\n");
cases--;
}
return 0;
}
[/c]

If you could help me ...
Thanks, Aur

[Larry]

Shouldn't you at least check to make sure the j's and the i's are in bound after the math?

[choyon_buet]

i also got TLE at first. My problem was that,i didn't check if the array index is negative or not.suppose when u r at the right most corner of the path , u can not check the postion to the further right.
or if u r at the left most position u can not check the further left character.
then the array index would be negativel. same check is needed when u r at the top of the rows.i got TLE first.but just after checking this ,i got accepted in .002 seconds:D

[soyoja]

I think that it is very simple problem.
I solved this problem using Depth-First Search algorithm.

In this problem, this hint showed...

Each of the letters in "IEHOVA" and the characters '@' and '#' appear exactly once in each test case.

So I think that this problem can solve using completed search.
But I want to use DFS. If this problem required more difficult
test case, then we must use DFS.

[Subeen]

i m also getting WA. can u help me?
[c]CODE REMOVED[/c]

[chicapi]

Careful with this:
[cpp]if(grid[0][j]=='@')[/cpp]
You should check if [cpp]if(grid[m-1][j]=='@')[/cpp]
'@' is in the last row.

[Subeen]

thanks for ur reply. now i got it AC. sometimes i do so silly mistakes

[chicapi]

Oh, you are lucky...!!!! I always make silly mistakes.... hehe

[vahid sanei]

I got Acc with bfs method
but i can`t solve this problem with dfs and recursive method
how can i solve this problem with rec ?
plz send me ,your acc code with recursive method,
thanks in advance