Peter's Escape

View as PDF

Points: 10 (partial)
Time limit: 1.8s
Memory limit: 256M

Authors:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Peter the penguin is lost in an icy cave! Upon closer observation, he notices that he can represent the cave as an rectangle in the Cartesian plane. However, the ice is very slippery, and he can only stop and change directions when he slides onto one of rock patches. In addition to this, he fears getting lost, so he will only move parallel to the axes.

Peter, much like any other sane penguin, is adverse to sliding onto a rock patch, and as such, wishes to ask you a question: what is the minimum number of times he will do so while escaping the cave?

If there are two adjacent rock patches, (e.g. one at and another at ), they are counted separately (i.e. he has slid over rock patches).

Note: The cave is unbounded (i.e. there are no walls).

Input Specification

Line : two space separated integers, and .
Line : two space separated integers, and , Peter's starting position.
Line : an integer, .
Lines : two space separated integers, and , which represent the position of an obstacle. It is guaranteed that Peter's starting position will never be an obstacle.
Line : an integer, , the number of exits.
Lines , two integers, , and , the coordinates of an exit. It is guaranteed that Peter's starting position will never be an exit, and that no exit will contain an obstacle.

Output Specification

The output should consist of one integer, the minimum number of times Peter will slide over a rock patch while escaping the cave. If it is not possible to escape the cave, output -1 instead.

For of points, .

Sample Input

10 10
1 1
3
4 4
4 1
8 9
2
10 4
2 8

Sample Output

2

• commented on Aug. 30, 2017, 9:20 a.m.

What's wrong with my code? I WA test case 3 of batch 1 and test case 6 of batch 2, but I have no idea why it doesn't work. I've made up a few test cases but it works for all of them. I'm fairly certain there's no issue with how I'm storing the adjacent rocks, so is there a problem with my binary search?

• commented on Aug. 30, 2017, 12:13 p.m.
• commented on Jan. 1, 2017, 4:19 p.m.

If the penguin is sliding towards two rock patches, one behind the other, will it stop when it gets to the first rock patch, or slide over both? If it stops at the first rock patch will it still count as sliding over two rock patches?

• commented on Jan. 1, 2017, 4:23 p.m.

He will stop at the first one, and the patches are counted separately (i.e. 2 patches).

• commented on Jan. 1, 2017, 4:26 p.m.

So when the penguin stops at the first rock patch (that is connected to another rock patch), you must say that the penguin slid over 2 rock patches?

• commented on Jan. 1, 2017, 5:54 p.m.

No, you only count the number of individual squares which Peter slides on. If he were to stop at the first rock, it would count as 1. However, if he were to slide over both of them, then that would count as 2.

• commented on Jan. 1, 2017, 3:28 p.m.

what is the minimum number of time he will do so

I think it's "what is the minimum number of times."

• commented on Jan. 1, 2017, 3:52 p.m.

Thanks! It's been fixed.

• commented on Jan. 1, 2017, 2:37 p.m.

In how many directions can the penguin move?

• commented on Jan. 1, 2017, 2:41 p.m. edited

It would appear, judging by the sample case, only horizontally and vertically.

• commented on Jan. 1, 2017, 2:44 p.m. edited

Statement has been updated to reflect this.

• commented on Jan. 1, 2017, 4:45 p.m.

Follow-up question: Can Peter choose which direction he starts in?

• commented on Jan. 1, 2017, 5:53 p.m.

Yes.

• commented on Jan. 1, 2017, 11:32 a.m.

Peter will slide onto a rock patch and stop.

• commented on Jan. 1, 2017, 11:13 a.m. edited

(he has slides over 2 rock patches)

• commented on Jan. 1, 2017, 9:32 a.m.

Will the penguin stop if it hits a wall?

• commented on Jan. 1, 2017, 9:34 a.m.

What walls are you referring to? The cave is unbounded (not surrounded by walls). He'll just slide off to infinity.

• commented on Jan. 1, 2017, 11:12 a.m.

If so, wouldn't it be more appropriate to represent the cave with a rectangle that is infinitely large? What would be the point of or then?

• commented on Jan. 1, 2017, 11:17 a.m. edited

For a more convenient representation of subtasks.

• commented on Jan. 1, 2017, 9:28 a.m.

If a penguin slides over an exit, will it stop at the exit or overshoot the exit? (assuming no rocks are nearby)

• commented on Jan. 1, 2017, 9:31 a.m. edit 3

Yes, he will always stop at the exit