676 - Horse Step Maze

All about problems in Volume 6. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

676 - Horse Step Maze

Post by Caesum » Tue Jan 14, 2003 8:16 pm

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 ?

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Re: 676 Horse Step Maze

Post by Ivan Golubev » Tue Jan 14, 2003 9:12 pm

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

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Wed Jan 15, 2003 1:04 am

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);

hs
New poster
Posts: 5
Joined: Mon Nov 05, 2001 2:00 am

Post by hs » Wed Jan 15, 2003 4:29 pm

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?

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Thu Jan 16, 2003 9:20 pm

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.

hs
New poster
Posts: 5
Joined: Mon Nov 05, 2001 2:00 am

Post by hs » Sat Jan 18, 2003 5:32 pm

Thanks for your help Adrian. My solution still needs some work.

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum » Sat Jan 18, 2003 9:24 pm

My solution gives 29957 steps also, but I get a sigxfsz error when I submit it :(

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum » Sat Jan 18, 2003 9:31 pm

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

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Is there any

Post by Whinii F. » Sun Jan 19, 2003 11:19 am

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.

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum » Sun Jan 19, 2003 1:29 pm

fail cases: try
(1,1)
(1,2)

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. » Sun Jan 19, 2003 6:26 pm

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?

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Jan 19, 2003 6:33 pm

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.

Fali
New poster
Posts: 8
Joined: Fri Jul 15, 2005 4:00 am

I got OLE... help

Post by Fali » Wed Jun 28, 2006 12:07 pm

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;
}

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Re: I got OLE... help

Post by daveon » Sun Aug 13, 2006 5:13 pm

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.

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman » Sat Sep 02, 2006 9:41 am

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.
You should never take more than you give in the circle of life.

Post Reply

Return to “Volume 6 (600-699)”