Page 1 of 1

295 - Fatman

Posted: Fri Oct 19, 2007 5:39 pm
by ..
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.

Posted: Sat Oct 27, 2007 11:51 pm
by 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.

Posted: Sun Oct 28, 2007 5:22 am
by ..
oh yes :o
I completely forget this is a maze....
I need to find a new algorithm, thanks a lot.

Re: 295 Fatman

Posted: Thu Aug 19, 2010 7:28 pm
by 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