Shortest Path in Maze with Portals

You are given a maze represented as a grid with n rows and m columns. Each cell of the maze is either:

• . indicating an open cell,
• # indicating an obstacle, or
• P representing a portal.

When you step on a portal cell P, you can instantly teleport to any other portal cell in the maze. However, the portals can only be used once (i.e. after using any portal teleportation, all portals become unusable for further teleportation). The start and destination cells will never be obstacles.

Your task is to compute the shortest path (in terms of number of steps) from a given start position to a destination position. Movement is allowed in the four cardinal directions (up, down, left, right) into open cells (cells that are not obstacles). If there is no valid path, output -1.

The distance is defined as the number of moves required. Formally, if you are at cell \( (x, y) \) and the destination is \( (x', y') \), you want to find the smallest \( d \) such that there exists a sequence of valid moves where:

\[ d = \min \{ k : (x_k, y_k) = (x', y') \} \]

inputFormat

The input is given via standard input in the following format:

<n> <m>
<row1>
<row2>
... 
<row n>
<start_x> <start_y>
<end_x> <end_y>

Here, <n> and <m> are the number of rows and columns. Each of the next n lines contains a string of length m representing the maze row, using characters ., #, or P. Then, the next line contains the start position coordinates and the following line contains the end position coordinates. All coordinates are zero-indexed.

outputFormat

Output a single integer representing the length of the shortest path from the start to the destination. If no such path exists, output -1.

## sample

5 5
.....
.#.#.
.#.#.
..P..
.#.#.
0 0
4 4

8