CCC '08 S3 - Maze

View as PDF

Submit solution

Points: 7
Time limit: 1.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


Output for Sample Input



  • 4
    Jinx  commented on Dec. 23, 2021, 10:40 a.m.

    I'd do it for free just for the pizza

  • 2
    JohnstonLiu  commented on Sept. 22, 2020, 2:41 p.m.

    I tested with the test data from Waterloo directly and I pass all the cases on there but when I submit it on DMOJ it gives me an entirely different output.

    • 8
      Jonathan_Uy  commented on Sept. 22, 2020, 3:25 p.m.

      To add on to what chika said, you can fix this by filling your visited and distance arrays with false and 0 at the start of your BFS method.

      However, your code would still be incorrect for the following case:


      Your code would print 2, while the correct answer is -1.

    • 6
      chika  commented on Sept. 22, 2020, 3:12 p.m.

      Your code has undefined behavior, this is almost always the case for programs that look deterministic but have different outputs when run on different systems.

      When I run your code locally, I get the following error:

      ccc08s3.cpp:45:41: runtime error: load of value 7, which is not a valid value for type 'bool'

      This sounds like a memory corruption issue.

  • 6
    cyopotatoe  commented on July 10, 2020, 11:33 p.m.

    This reminds me of that hidden google game I forgot what it was called but Cewl

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

    This comment is hidden due to too much negative feedback. Show it anyway.

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

      minimum number of intersections required to pass through

      enter image description here

  • 22
    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.


    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.


    • 15
      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.

    • 9
      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.