A maze is a rectangular grid, where each cell is either an empty space or an obstacle. The Prince of Persia is initially positioned in one empty cell, and the Princess is in another one.
Each of them can move from one empty cell to another one only if these cells are adjacent, i. e., share a common side. None of them can appear in a cell with an obstacle.
Their common target is to move into the same cell.
The terrible usurper Jaffar doesn't want that to happen. He is going to put obstacles into some currently empty cells in order to prevent their meeting. He cannot put the obstacles in the cells where the Prince and the Princess are initially located, but he can use any other empty cells.
You will be given a String maze containing empty cells ('.'), obstacles ('#') and the initial positions of the Prince and the Princess ('P').
Return the minimum number of obstacles that Jaffar must put to separate the Prince and the Princess. If he is unable to separate them, return -1.
|-||maze will contain between 1 and 10 elements, inclusive.|
|-||Each element of maze will contain between 1 and 10 characters, inclusive.|
|-||Each element of maze will contain the same number of characters.|
|-||Each element of maze will contain only dots ('.'), number signs ('#') and uppercase 'P' characters.|
|-||There will be exactly two 'P' characters in the elements of maze.|