CCC '08 S3 - Maze
View as PDFCanadian 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
Comments
How is the scooter powered by pizza when you already ate the pizza?
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.
Can
and 
have lengths of 
?
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).
So would I put 1 or 0 if the case is both 1s?
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.
The starting position will never be *
I'd do it for free just for the pizza
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.
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.
Thanks!
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.
This reminds me of that hidden google game I forgot what it was called but Cewl
This comment is hidden due to too much negative feedback. Show it anyway.
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.
Your code exhibits undefined behavior. The array size of
gridis not correct; it should be 20 by 21.scanfwill automatically append a\0character 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\0from 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 invisited, but sincevisitedis initially set to 0, there will be no visible difference there.The fact that you got
ACon wcipeg is a mere coincidence.There are cases of undefined behaviour leading to time travel.
Thanks for the explanation!
^^ 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