868 - Numerical Maze

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

Moderator: Board moderators

Evan Tsang
New poster
Posts: 11
Joined: Sun Jan 02, 2005 9:14 am

868 - Numerical Maze

Post by Evan Tsang » Mon Jan 17, 2005 4:02 am

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
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by stubbscroll » Tue Jan 18, 2005 9:20 am

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
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Sat Feb 05, 2005 12:26 am

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!
Last edited by Emilio on Wed Mar 23, 2005 7:56 pm, edited 1 time in total.

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by stubbscroll » Tue Feb 08, 2005 5:21 am

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

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Wed Feb 09, 2005 9:21 pm

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:

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by stubbscroll » Thu Feb 10, 2005 4:10 am

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
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Thu Feb 10, 2005 12:01 pm

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

Thanks another time.

User avatar
Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

Post by Christian Schuster » Sun Feb 20, 2005 2:07 am

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
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Sun Feb 20, 2005 4:37 am

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

User avatar
Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

Post by Christian Schuster » Sun Feb 20, 2005 7:57 pm

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

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by stubbscroll » Mon Feb 21, 2005 3:12 am

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.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Tue Feb 22, 2005 1:51 pm

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.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Sat Mar 19, 2005 2:00 pm

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.

User avatar
danielrocha
New poster
Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil
Contact:

Post by danielrocha » Mon Sep 05, 2005 7:54 pm

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.
Daniel
UFRN HDD-1
Brasil

pandaben7890
New poster
Posts: 1
Joined: Thu Apr 03, 2008 6:11 am

Re: 868 Numerical Maze

Post by pandaben7890 » Fri Apr 04, 2008 6:06 am

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

Post Reply

Return to “Volume 8 (800-899)”