CCC '08 S3 - Maze

View as PDF

Submit solution

Points: 10
Time limit: 2.0s
Memory limit: 64M

Problem type
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

Comments


  • 0
    DarthVader336  commented on Aug. 31, 2018, 11:04 p.m.

    For the second case, there are only four ways. How are there seven?


    • 10
      KevinLu  commented on Sept. 1, 2018, 2:03 p.m.

      minimum number of intersections required to pass through

      enter image description here


  • 17
    BMP  commented on May 26, 2015, 11:28 p.m. edited

    I have a question regarding compilers, I attempted this problem on WCIPEG with a C++11 compiler and got 3/5. Then, I re-submitted the same exact code with a regular C++ compiler and got 5/5. Here, I keep getting 3/5 with every compiler I try, using the same code I used on PEG.

    Submission

    I'm also positive that my outputs are right (tested them, since they're provided in the analysis section when you solve a problem), since DMOJ and PEG use the same cases, and I've solved this problem a while back.

    Thanks.


    • 12
      FatalEagle  commented on May 27, 2015, 9:23 a.m.

      Your code exhibits undefined behavior. The array size of grid is not correct; it should be 20 by 21. scanf will automatically append a \0 character to the end of the string it reads in, but you only reserved 20 spaces when you should have reserved 21. What most probably happened (but is not guaranteed to happen, since this is still undefined behavior) is that the trailing \0 from one line had overwritten the first character in the next line, filling the first element of each row in your array with \0. It would also perform overwrite one more byte of memory in visited, but since visited is initially set to 0, there will be no visible difference there.

      The fact that you got AC on wcipeg is a mere coincidence.


    • 7
      fifiman  commented on May 27, 2015, 12:11 a.m. edit 3

      ^^ Had the same happen many times on other problems.

      Proof : Two of the same submission, just different languages.

      http://s21.postimg.org/rsczt6o3b/image.png