868 - Numerical Maze

[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

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

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

[stubbscroll]

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

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

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

[Emilio]

I'll try it, I hope get AC, I can't understand the cause of my bug.

Thanks another time.

[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

[Emilio]

Hi Christian,
One question, Can you use more once the same number(grid) for a solution?
Thanks

[Christian Schuster]

No, you may not use a grid cell twice. At least I got AC with that assumption.

[stubbscroll]

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.

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

Thanks another time.

[Emilio]

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

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

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