Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ### Canadian Computing Competition: 2008 Stage 1, Senior #3
- In order to make a few dollars, you have decided to become part of a scientific experiment. You are fed lots of pizza, then more pizza and then you are asked to find your way across the city on a scooter powered only by pizza. Of course, the city has lots of intersections, and these intersections are very controlled. Some intersections are forbidden for you to enter; some only let you move north/south as you leave the intersection; others let you move only east/west as you leave the intersection; and the rest let you go in any compass direction (north, south, east or west).
- Thankfully your scientific friends have given you a map of the city (on the back of a pizza box), with an arrangement of symbols indicating how you can move around the city. Specifically, there are 4 different symbols on the box:
- * The symbol `+` indicates we can move in any direction (north/south/east/west) from this location.
- * The symbol `-` indicates we can move only east or west from this location.
- * The symbol `|` indicates we can move only north or south from this location.
- * The symbol `*` indicates we cannot occupy this location.
- Your task is to determine how many intersections you must pass through to move from the north-west corner of the city to the south-east corner of the city.
- ## Input Specification
- The input begins with a number ~t~ ~(1 \le t \le 10)~ on its own line, which indicates how many different cases are contained in this file. Each case begins with a number ~r~ on one line, followed by a number ~c~ on the next line ~(1 \le r, c \le 20)~. The next ~r~ lines contain ~c~ characters, where each character is one of {`+`, `*`, `-`, `|`}. You may assume the north-west corner of the city can be occupied (i.e., it will not be marked with `*`).
- ## Output Specification
- The output will be ~t~ lines long, with one integer per line. The integer on line ~i~ ~(1 \le i \le t)~ indicates the minimum number of intersections required to pass through as you move from the north-west corner of the city to the south-east corner of the city. If there is no way to get from the north-west corner to the south-east corner, output `-1` for that test case.
- ## Sample Input
- 3
- 2
- 2
- -|
- *+
- 3
- 5
- +||*+
- +++|+
- **--+
- 2
- 3
- +*+
- +*+
- ## Output for Sample Input
- 3
- 7
- -1
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement