Page 1 of 2

868 - Numerical Maze

Posted: Mon Jan 17, 2005 4:02 am
by Evan Tsang
Can a path reuse a visited position?

Code: Select all

1 X X X
1 X X X
2 3 1 X
1 X 2 X
X X 3 4
Is this a valid path?

-evan

Posted: Tue Jan 18, 2005 9:20 am
by stubbscroll
I could not find any mention in the problem description about visiting positions more than once... But my AC program finds no valid path for your example.

Posted: Sat Feb 05, 2005 12:26 am
by Emilio
Hello,
I have seen this post, and I have decided to make three questions :)

1) Are there some tricky inputs?
2) When in the problem specification says
the exit point is always a cell in the last line of the maze
that is refered only for the last row, or for the other edges of the maze too?
3) Why is my code wrong?

Code: Select all

cut -after AC
Thanks in advance!

Posted: Tue Feb 08, 2005 5:21 am
by stubbscroll
Emilio wrote:Hello,
I have seen this post, and I have decided to make three questions :)

1) Are there some tricky inputs?
2) When in the problem specification says
the exit point is always a cell in the last line of the maze
that is refered only for the last row, or for the other edges of the maze too?
3) Why is my code wrong?

Thanks in advance!
1) Not that I know of.
2) Only the last row. Otherwise, a 1 in one of the top corners would solve the maze instantly...
3) I haven't studied it, but it fails on this input:

Code: Select all

1

6 6
1 1 2 1 2 3
2 1 4 3 2 1
3 4 5 1 2 3
3 2 1 6 5 4
4 5 6 7 1 2
9 9 9 9 9 3
Your output:

Code: Select all

1 7
6 0
Correct output:

Code: Select all

1 1
6 6

Posted: Wed Feb 09, 2005 9:21 pm
by Emilio
Thanks,

I have changed this line

Code: Select all

 if (next == tope && x == F) 
by this

Code: Select all

if (x == F) 
and now my output is the same that yours, but I get WA.
I thought that the finish of the serie would must finish always with the last number of this. For example 1; 1,2; 1,2,3; 1,2,3,4; ... and so. But in your test example 1; 1,2; 1,2,3; 1,2,3,4; 1,2,3,4,5; 1,2,3,4,5,6; 1,2,3,4,5,6,7; 1,2,3; and finish.

Any hint more?
What is my bug, please? I can't encounter it. :cry:

Posted: Thu Feb 10, 2005 4:10 am
by stubbscroll
Sorry, I am terrible at reading other people's code, so I don't know what your bug is (in addition, I get more confused when identifiers are written in another language than English). I got AC on my first try at this problem and I don't have any more I/O data to offer. I can only offer some general wisdom:

- create a program to generate random I/O. A good way for this problem is to first generate a random grid of numbers, pick a random point in the top row, move in random directions (UDLR) while inserting 1121231234... until you reach bottom row (make sure the path doesn't use the same square twice), this way each position is guaranteed to have a solution.
- rewrite from scratch and compare the outputs from both programs against each other, and work from there.

I know these hints are a lot of work, but they might help you on some problems.

Posted: Thu Feb 10, 2005 12:01 pm
by Emilio
I'll try it, I hope get AC, I can't understand the cause of my bug.

Thanks another time.

Posted: Sun Feb 20, 2005 2:07 am
by Christian Schuster
Hi there, just got it AC after several submissions. And yes, the last subsequence of the path must be complete, but I think the phrase
The path consists of subsequences obeying to the following rule: 1; 1,2; 1,2,3; 1,2,3,4; and so on.
doesn't state this clearly enough.

HTH,
Christian

Posted: Sun Feb 20, 2005 4:37 am
by Emilio
Hi Christian,
One question, Can you use more once the same number(grid) for a solution?
Thanks

Posted: Sun Feb 20, 2005 7:57 pm
by Christian Schuster
No, you may not use a grid cell twice. At least I got AC with that assumption. ;)

Posted: Mon Feb 21, 2005 3:12 am
by stubbscroll
Christian Schuster wrote:Hi there, just got it AC after several submissions. And yes, the last subsequence of the path must be complete, but I think the phrase
The path consists of subsequences obeying to the following rule: 1; 1,2; 1,2,3; 1,2,3,4; and so on.
doesn't state this clearly enough.
Strange, I got AC without considering the above rule.

Posted: Tue Feb 22, 2005 1:51 pm
by Emilio
Hi another time,
I think that it's a bit strange, you can solve this problem with two different approachs.
I think that it's an easy problem but it has a low rate of accepted submissions.
I tried it using all those different approachs and always got WA. :(
Well, I'll try another time later and if got AC I'll post it here. :D

Thanks another time.

Posted: Sat Mar 19, 2005 2:00 pm
by Emilio
AAAAAAARRRRRRRRRRRGGGGGGGGGGHHHHHHHHH! :x
I have got AC now.
The problem is very easy. The unique trouble was test cases with multiple solution. Now this is corrected with the new specification. Before you could get AC depending on the order of the movements. This is a reason for I think some AC actually can be WA really.

Posted: Mon Sep 05, 2005 7:54 pm
by danielrocha
Just to make it clear: the last cell to be visited MUST BE the end of a sequence. This bothered me when I was solving this problem. I'm not sure if there are inputs where there are no solutions but my AC problem prints just an empty line.

Re: 868 Numerical Maze

Posted: Fri Apr 04, 2008 6:06 am
by pandaben7890
I have try everything here. But I still don't know why i get WA. I would be glad if someone can find my mistake. Thanks in advance.

Code: Select all

#include<stdio.h>

short height,width,maze[30][30],end=0,point;

void search(short level,short run,short y,short x)
{
  short a,b,temp,temps;
  
  if(y==height && run==1)
  {
    printf("%hd %hd\n%hd %hd\n",1,point,y,x);
    end=1;
    return;
  }
  
  if(level==1 && end==0)
  {
    for(a=1;a<=width && end==0;a++)
    {
      if(maze[1][a]==1)
      {
        temp=maze[1][a];
        maze[1][a]=0;
        point=a;
        search(2,1,1,a);
        maze[1][a]=temp;
      }
    }
  }
  else if(end==0)
  {
    a=y;
    b=x-1;
    if(maze[a][b]==run && end==0)
    {
      run++;
      temp=0;
      if(run==level+1)
      {
        level++;
        run=1;
        temp=1;
      }
      temps=maze[a][b];
      maze[a][b]=0;
      search(level,run,a,b);
      maze[a][b]=temps;
      if(temp==0)
        run--;
      else
      {
        level--;
        run=level;
      }
    }
    a=y+1;
    b=x;
    if(maze[a][b]==run && end==0)
    {
      run++;
      temp=0;
      if(run==level+1)
      {
        level++;
        run=1;
        temp=1;
      }
      temps=maze[a][b];
      maze[a][b]=0;
      search(level,run,a,b);
      maze[a][b]=temps;
      if(temp==0)
        run--;
      else
      {
        level--;
        run=level;
      }
    }
    a=y-1;
    b=x;
    if(maze[a][b]==run && end==0)
    {
      run++;
      temp=0;
      if(run==level+1)
      {
        level++;
        run=1;
        temp=1;
      }
      temps=maze[a][b];
      maze[a][b]=0;
      search(level,run,a,b);
      maze[a][b]=temps;
      if(temp==0)
        run--;
      else
      {
        level--;
        run=level;
      }
    }
    a=y;
    b=x+1;
    if(maze[a][b]==run && end==0)
    {
      run++;
      temp=0;
      if(run==level+1)
      {
        level++;
        run=1;
        temp=1;
      }
      temps=maze[a][b];
      maze[a][b]=0;
      search(level,run,a,b);
      maze[a][b]=temps;
      if(temp==0)
        run--;
      else
      {
        level--;
        run=level;
      }
    }
  }
}

int main()
{
  short a,b,c,cases;
  
  scanf("%hd",&cases);
  
  for(c=0;c<cases;c++)
  {
    scanf("%hd %hd",&height,&width);
    for(a=0;a<=height+1;a++)
    {
      if(a==0 || a==height+1)
        for(b=0;b<=width;b++)
          maze[a][b]=0;
      else
      {
        maze[a][0]=0;
        for(b=1;b<=width;b++)
          scanf("%hd",&maze[a][b]);
      }
      maze[a][b]=0;
    }
    
    point=0;
    end=0;
    search(1,1,0,0);
    if(c!=cases-1)
      printf("\n");
  }
  
  return 0;
}