Pizza-Powered Scooter Navigation

You have joined a quirky scientific experiment where you must traverse a city on a scooter powered solely by pizza. The city is laid out on a grid of intersections, and each intersection is marked with a symbol that indicates the allowed directions of travel:

• + : You can move in any of the four compass directions: north, south, east, or west.
• - : You can only move east or west.
• | : You can only move north or south.
• * : This intersection is blocked and cannot be entered.

The map is provided on a pizza box. You are to determine the minimum number of intersections you must pass through (including the starting and ending intersections) to travel from the northwest (top-left) corner of the grid to the southeast (bottom-right) corner. If no valid path exists, output -1.

The movement restrictions are summarized below in \( \LaTeX \):

For an intersection with symbol \( s \), the allowed movements \( D(s) \) are given by:

\[ D(s) = \begin{cases} \{(0,1), (0,-1), (1,0), (-1,0)\} & \text{if } s = '+' \ \{(0,1), (0,-1)\} & \text{if } s = '-' \ \{(1,0), (-1,0)\} & \text{if } s = '|' \ \emptyset & \text{if } s = '*' \end{cases} \]

inputFormat

The first line contains two integers \( n \) and \( m \) (the number of rows and columns, respectively). The following \( n \) lines each contain a string of length \( m \), representing the grid. Each character is one of +, -, |, or *.

outputFormat

Output a single integer which is the minimum number of intersections passed (including the start and destination) to go from the top-left corner to the bottom-right corner. If no path exists, output -1.

sample

3 3
+-+
|*|
+-+

5