## 10452 - Marcus

Moderator: Board moderators

amd-RS
New poster
Posts: 27
Joined: Thu Sep 05, 2002 7:37 am

### 10452 - Marcus

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

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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
New poster
Posts: 4
Joined: Wed Feb 12, 2003 5:00 pm

### 10452 Why my code doesn't work?

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%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
New poster
Posts: 27
Joined: Thu Sep 05, 2002 7:37 am
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``

Code: Select all

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

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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
New poster
Posts: 4
Joined: Wed Feb 12, 2003 5:00 pm
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
New poster
Posts: 27
Joined: Thu Sep 05, 2002 7:37 am
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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Shouldn't you at least check to make sure the j's and the i's are in bound after the math?

choyon_buet
New poster
Posts: 5
Joined: Mon Feb 24, 2003 5:28 pm
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
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:
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
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Contact:
i m also getting WA. can u help me?
[c]CODE REMOVED[/c]
Last edited by Subeen on Thu Aug 21, 2003 5:03 pm, edited 1 time in total.

chicapi
New poster
Posts: 6
Joined: Thu Apr 24, 2003 9:08 pm
Location: Buenos Aires
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.
maru 3.1415926

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Contact:
thanks for ur reply. now i got it AC. sometimes i do so silly mistakes

chicapi
New poster
Posts: 6
Joined: Thu Apr 24, 2003 9:08 pm
Location: Buenos Aires
Oh, you are lucky...!!!! I always make silly mistakes.... hehe
maru 3.1415926

vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

### Re: 10452 - Marcus, help!

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,