[CCC 2008 S3] Maze

Luogu

IDLGP9860

Time1000ms

Memory128MB

DifficultyP2

2008CCC（加拿大）

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 northwest corner of the city to the south-east corner of the city. ## Input The input begins with a number $t (1 \leq t \leq 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 \leq r, c \leq 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 The output will be $t$ lines long, with one integer per line. The integer on line $i (1 \leq i \leq 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. [samples]

Samples

Input #1

3
2
2
-|
*+
3
5
+||*+
+++|+
**--+
2
3
+*+
+*+

Output #1

3
7
-1

API Response (JSON)

{
  "problem": {
    "name": "[CCC 2008 S3] Maze",
    "description": {
      "content": "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 scoo",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9860"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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 scoo...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments