## 295 - Fatman

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

Moderator: Board moderators

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

### 295 - Fatman

Could anyone kindly give some test case?

I have no idea if my algorithm ok. Consider the sample input:
1
8 5
8
2 1
1 3
3 2
4 4
5 3
6 4
7 2
7 1
For each combination of obstacle(along x-axis), I consider a "tunnel" that is formed by "ceiling" and "floor", which are both series of segment.
Say ceiling is "(1,3) (2, 5) (3, 5) (4, 4) ..." and floor is "(1, 0) (2, 1) (3, 2) (4, 0)...." Then I output the minimum pairwise of the vertex forming the tunnel.
My signature:
• Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:
If I understood your algorithm correctly, it will give wrong answer to both of these cases:

Code: Select all

``````2
9 6
18
1 2
2 2
3 2
4 2
5 2
6 2
1 3
1 4
1 5
8 1
8 2
8 3
8 4
7 4
6 4
5 4
4 4
3 4
4 10
12
1 4
1 5
1 6
1 7
1 8
1 9
3 1
3 2
3 3
3 4
3 5
3 6
``````
The first case is a zigzag maze where the man must go right, down, left, down, right. The second case is a passage with two "walls" close to each other, with wide openings. Your algorithm would return 1 and 4 for these tests, while the correct answer is 2.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
oh yes
I completely forget this is a maze....
I need to find a new algorithm, thanks a lot.
My signature:
• Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

gt1404
New poster
Posts: 6
Joined: Sat Dec 26, 2009 10:16 am

### Re: 295 Fatman

Anybody have any test cases. Everything I have checks out with the solution by hand including mazes and L=0, W=0 cases. I'm failing around the 1 second mark, did anyone have an issue with rounding here???