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.

[stubbscroll]

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.

[..]

oh yes
I completely forget this is a maze....
I need to find a new algorithm, thanks a lot.

[gt1404]

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

Thanks in advance
-gt