Page 1 of 2
676 - Horse Step Maze
Posted: Tue Jan 14, 2003 8:16 pm
by Caesum
Seems like a simple enough problem, but I notice low acceptance rates on it. My program dies with:
Your program has died with signal 25 (SIGXFSZ). Meaning:
File size limit exceeded
which makes no sense since it doesnr use files and the problem does not have a special judge or anything. So two questions:
1. Any special considerations for this question ?
2. Anyone seen sigxfsz before ?
Re: 676 Horse Step Maze
Posted: Tue Jan 14, 2003 9:12 pm
by Ivan Golubev
Caesum wrote:2. Anyone seen sigxfsz before ?
Yes, I've got this error two times when solving (actually speeding up) P495. But I have no idea what it means. I've asked one man from OJ team about this SIGXFSZ but he's also wasn't able to say what this error means!
Posted: Wed Jan 15, 2003 1:04 am
by Adrian Kuegel
The only special case is if the starting point is the same as the end point, print only the start point, not the end point.
Perhaps also the reading part is critical (I don't think so); here is how I read the input:
scanf("( %d , %d ) ( %d , %d ) ",&sx,&sy,&ex,&ey);
Posted: Wed Jan 15, 2003 4:29 pm
by hs
I keep getting wrong answer.
What should we count as a step?
Can anyone post a case that is near the limits (50000 steps) and giving the number of steps?
Posted: Thu Jan 16, 2003 9:20 pm
by Adrian Kuegel
You should also count a backtracking step as step.
Here an example:
The number of steps for the input
(8,4)
(9,5)
is 29957.
Posted: Sat Jan 18, 2003 5:32 pm
by hs
Thanks for your help Adrian. My solution still needs some work.
Posted: Sat Jan 18, 2003 9:24 pm
by Caesum
My solution gives 29957 steps also, but I get a sigxfsz error when I submit it
Posted: Sat Jan 18, 2003 9:31 pm
by Caesum
nevermind, i resubmitted it and it gave ole instead of the sigfsx error - (no changes to the source though), anyway, fixed a stupid bug and got ac
Is there any
Posted: Sun Jan 19, 2003 11:19 am
by Whinii F.
Are there any "fail" cases? I've tried it for every starting & ending position combinations and couldn't find one..
Isn't it "fail" when the mouse attempts to backtrack from its original position?
The output specification in the problem statement mentions:
The coordinates of the walking path from the starting point to the ending point or ``fail''.
It confuses me
Help! I've been getting too much WAs. :'(
Thanks in advance.
Posted: Sun Jan 19, 2003 1:29 pm
by Caesum
fail cases: try
(1,1)
(1,2)
Posted: Sun Jan 19, 2003 6:26 pm
by Whinii F.
Oh, thanks, but..
Now I got that 'failed' cases can be found when analyzing beyond the 50000th step. But, removing the break-up routine when the 50000th step is reached, gives out TLE.
What shall I do? :'(
Is there a trick in the input, or it's just my program's matter?
How can I detect 'failed' cases easily?
Posted: Sun Jan 19, 2003 6:33 pm
by Adrian Kuegel
Think of the board as a chess board with black and white fields. When you start on a "white" field, what happens when you move? Think about it, and then you will see how to determine failed cases.
I got OLE... help
Posted: Wed Jun 28, 2006 12:07 pm
by Fali
Hi, can you give me some input/output test please, i have a mistake, here is my code, if you see something wrong please tell me.
Code: Select all
/*
Horse Step Maze, UVa # 676
Nephtali Garrido
27/06/06
*/
#include <cstdio>
#include <iostream>
using namespace std;
int n,c,c2;
bool mat[9][9],ya;
char xi,yi,xf,yf,x;
void busca(int x, int y)
{ if(x!=xi || y!=yi)
printf(", (%d,%d)",x+1,y+1);
if(x==xf && y==yf)
{ ya=true;
return;
}
mat[x][y]=true;
if(x>0 && y<8 && mat[x-1][y+1]==false)
{ busca(x-1,y+1);
if(ya==true)
return;
printf(", (%d,%d)",x+1,y+1);
}
if(x<8 && y<8 && mat[x+1][y+1]==false)
{ busca(x+1,y+1);
if(ya==true)
return;
printf(", (%d,%d)",x+1,y+1);
}
if(x<8 && y>0 && mat[x+1][y-1]==false)
{ busca(x+1,y-1);
if(ya==true)
return;
printf(", (%d,%d)",x+1,y+1);
}
if(x>0 && y>0 && mat[x-1][y-1]==false)
{ busca(x-1,y-1);
if(ya==true)
return;
printf(", (%d,%d)",x+1,y+1);
}
mat[x][y]=false;
return;
}
int main()
{ scanf("%d",&n);
while(n>0)
{ n--;
cin>>x>>xi>>x>>yi>>x>>x>>xf>>x>>yf>>x;
xi-=('0'+1);yi-=('0'+1);xf-=('0'+1);yf-=('0'+1);
if((xi+yi)%2==(xf+yf)%2)
{ for(c=0;c<9;c++)
for(c2=0;c2<9;c2++)
mat[c][c2]=false;
if(xi!=xf || yi!=yf)
{ ya=false;
printf("(%d,%d)",xi+1,yi+1);
busca(xi,yi);
}
else
printf("(%d,%d)",xi+1,yi+1);
}
else
printf("fail");
printf("\n");
}
return 0;
}
Re: I got OLE... help
Posted: Sun Aug 13, 2006 5:13 pm
by daveon
Fali wrote:Hi, can you give me some input/output test please, i have a mistake, here is my code, if you see something wrong please tell me.
You did not handle the 50000+ step case at all.
Posted: Sat Sep 02, 2006 9:41 am
by Mohammad Mahmudur Rahman
This problem is leaving me completely dumb. Already got about a dozen WAs today though I miserably failed to find a possible reason. It will be greatly helpful if someone who has gotten AC in this one can provide me some sample I/O.