### 868 - Numerical Maze

Posted:

**Mon Jan 17, 2005 4:02 am**Can a path reuse a visited position?

Is this a valid path?

-evan

Code: Select all

```
1 X X X
1 X X X
2 3 1 X
1 X 2 X
X X 3 4
```

-evan

Page **1** of **2**

Posted: **Mon Jan 17, 2005 4:02 am**

Can a path reuse a visited position?

Is this a valid path?

-evan

Code: Select all

```
1 X X X
1 X X X
2 3 1 X
1 X 2 X
X X 3 4
```

-evan

Posted: **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.

Posted: **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

3) Why is my code wrong?

Thanks in advance!

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

that is refered only for the last row, or for the other edges of the maze too?the exit point is always a cell in the last line of the maze

3) Why is my code wrong?

Code: Select all

```
cut -after AC
```

Posted: **Tue Feb 08, 2005 5:21 am**

1) Not that I know of.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 saysthat is refered only for the last row, or for the other edges of the maze too?the exit point is always a cell in the last line of the maze

3) Why is my code wrong?

Thanks in advance!

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

Code: Select all

```
1 1
6 6
```

Posted: **Wed Feb 09, 2005 9:21 pm**

Thanks,

I have changed this lineby this 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.

I have changed this line

Code: Select all

```
if (next == tope && x == F)
```

Code: Select all

```
if (x == F)
```

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.

Posted: **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.

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

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

Thanks another time.

Thanks another time.

Posted: **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

HTH,

Christian

doesn't state this clearly enough.The path consists of subsequences obeying to the following rule: 1; 1,2; 1,2,3; 1,2,3,4; and so on.

HTH,

Christian

Posted: **Sun Feb 20, 2005 4:37 am**

Hi Christian,

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

Thanks

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

Thanks

Posted: **Sun Feb 20, 2005 7:57 pm**

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

Strange, I got AC without considering the above rule.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 phrasedoesn't state this clearly enough.The path consists of subsequences obeying to the following rule: 1; 1,2; 1,2,3; 1,2,3,4; and so on.

Posted: **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.

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

Posted: **Sat Mar 19, 2005 2:00 pm**

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.

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

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.

Posted: **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;
}
```