시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 83 | 36 | 32 | 45.714% |
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:
Your task is to determine how many intersections you must pass through to move from the northwest corner of the city to the south-east corner of the city.
The input begins with a number t (1 ≤ t ≤ 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 ≤ r, c ≤ 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 *).
The output will be t lines long, with one integer per line. The integer on line i (1 ≤ i ≤ 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.
3 2 2 -| *+ 3 5 +||*+ +++|+ **--+ 2 3 +*+ +*+
3 7 -1