## CCC '08 S3 - Maze

View as PDF

Points: 7
Time limit: 1.0s
Memory limit: 256M

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 on its own line, which indicates how many different cases are contained in this file. Each case begins with a number on one line, followed by a number on the next line . The next lines contain 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 lines long, with one integer per line. The integer on line 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

• commented on Jan. 1, 2024, 7:29 p.m. edit 2

Why does this give IR? I tested all the cases on my IDE and didn't get NullPointerException

https://dmoj.ca/submission/6043010

It even shows that my output is correct

Edit: I fixed the issue, my for loop went from to rather than to , so my code didn't actually finish executing after all cases were made.

• commented on Dec. 22, 2022, 8:51 p.m. edited

Can and have lengths of ?

• commented on Dec. 22, 2022, 11:01 p.m.

According to the input specification:

This means can be 1, yes (and you should assume that there is at least one case where they are both 1).

• commented on Dec. 23, 2022, 1:25 a.m.

So would I put 1 or 0 if the case is both 1s?

• commented on Jan. 21, 2023, 3:35 a.m. edited

Should be 1, as otherwise the test case would give 2, 6, -1. However, note that if the starting position is *, you should output -1.

• commented on March 27, 2023, 6:14 p.m.

You may assume the north-west corner of the city can be occupied

The starting position will never be *

• commented on Dec. 23, 2021, 3:40 p.m.

• commented on Sept. 22, 2020, 6: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.

• commented on Sept. 22, 2020, 7:25 p.m. edited

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:

1
2
+*

• commented on Sept. 22, 2020, 7:26 p.m.

Thanks!

• commented on Sept. 22, 2020, 7: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.

• commented on July 11, 2020, 3:33 a.m.

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

• commented on Sept. 1, 2018, 3:04 a.m.

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

• commented on Sept. 1, 2018, 6:03 p.m.

minimum number of intersections required to pass through

• commented on May 27, 2015, 3:28 a.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.

Thanks.

• commented on May 27, 2015, 1:23 p.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.

• commented on May 27, 2015, 11:47 p.m. edited
• commented on May 27, 2015, 2:26 p.m.

Thanks for the explanation!

• commented on May 27, 2015, 4: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