676 - Horse Step Maze

[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 ?

[Ivan Golubev]

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]

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]

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]

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]

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

[Caesum]

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

[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

[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.

[Caesum]

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

[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?

[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.

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

[daveon]

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]

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.