## 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

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

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``````

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
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
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:
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
I'll try it, I hope get AC, I can't understand the cause of my bug.

Thanks another time.

Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 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
Hi Christian,
One question, Can you use more once the same number(grid) for a solution?
Thanks

Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am
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:
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
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
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain
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
New poster
Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil
Contact:
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

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