Description
Again, Plankton is planning to steal Krabby Patty from Krusty Krab. This time he gives you a huuuuuuuuge 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. 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 a possible start position of Plankton.
5. 'O' means a portal. There may be many portals. Any 2 of the portals could reach each other within one step. A portal also could be reached in one step from 4 directions: up, down, left, and right.
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. Your task is to determine the start position of Plankton among all possible start positions and 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 '#', '.', '@', 'P', and 'O'.
Testcases 1-3: No portals and a single possible start position
Testcases 4-6: No portals
Testcases 7-8: No further constraints
Constraints:
- There are exactly one '@' on the map
- 5 <= n, m <= 1000
- There are no constraints on the numbers of possible start positions and portals, so be aware of time complexity.
Output
The first line contains an integer, specifying the minimum step count.
The second line contains two integers, a and b, which means the start position should be at the ath row and bth column. If there are more than one start position that has the minimum step count, print the upper one. If they are at the same row, print the left one.
If there is no way for plankton to reach Krabby Patty, print -1 in one line.