{"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 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).\n\nThankfully 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:\n\n- The symbol `+` indicates we can move in any direction (north/south/east/west) from this location.\n\n- The symbol `-` indicates we can move only east or west from this location.\n\n- The symbol `|` indicates we can move only north or south from this location.\n\n- The symbol `*` indicates we cannot occupy this location.\n\nYour 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.\n\n## Input\n\nThe 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\none of {`+`, `*`, `-`, `|`}. You may assume the north-west corner of the city can be occupied (i.e., it will not be marked with `*`).\n\n## Output\n\nThe 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.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9860","tags":["2008","CCC（加拿大）"],"sample_group":[["3\n2\n2\n-|\n*+\n3\n5\n+||*+\n+++|+\n**--+\n2\n3\n+*+\n+*+\n","3\n7\n-1"]],"created_at":"2026-03-03 11:09:25"}}