Description
Again, Plankton is planning to steal Krabby Patty from Krusty Krab. This time he gives you a huuuuge amount of money and asks you to plan a great path for him to approach Krabby Patty.
You are given a map with some information. The map is a grid and contains a character on each cell, and Plankton cannot go out of the map since his legs are too short. Here are the meanings of each character:
1. '#' means the obstacle. This cell is blocked and cannot be reached.
2. '.' means road. This cell could be reached in one step from 4 directions: up, down, left, and right.
3. '@' means the Krabby Patty. There would only be one Krabby Patty on the map.
4. 'P' means the start position of Plankton.
Plankton's goal is to find the minimum step count between him and Krabby Patty, i.e. the length of the shortest path between Plankton and Krabby Patty. Plankton wants to know how long does it take to reach Krabby Patty, so your task is to output the minimum step count.
Input
The first line contains two integers, n and m, which means there are n rows and m columns for the map.
Each of the next n lines contains a string with length m. The strings would only contain '#', '.', '@', and 'P'.
Constraints:
- There are exactly one '@' on the map
- 5 <= n, m <= 1000
Output
There is only one line for output, which contains an integer, specifying the minimum step count.
If there is no way for plankton to reach Krabby Patty, print -1 instead.