402348: GYM100735 C Power

Arthur, the superhero of our times, faces a confusing problem.

He almost completed his final mission. Only one step is left - to find the amulet of power. Well, Arthur knows where the amulet is. But it is not so easy to take him. The reason is that the powerful guard kills anybody who tries to steal the amulet. Unfortunately, the guard is much more powerful than Arthur. So if Arthur meets the guard, the end is not too good.

It is known that the amulet of power can not exist for a long time without the owner. So Arthur has to rush.

You are given the matrix which describes the forest. Arthur and the guard can not leave the forest. The forest contains some dangerous animals. For example, snakes or hungry wolfs. No doubt that Arthur and the guard are afraid of these animals.

Assume that Artur's position is (r_A;c_A) and the guard's position is (r_G;c_G). r, c describes the row and the column of the matrix. Let's define the guard's moves formally:

if c_A < c_G, the guard moves c_G:  = c_G - 1

if c_G < c_A, the guard moves c_G:  = c_G + 1 if the guard did not make the previous move (c_A = c_G or because of dangerous animals) then he moves with the respect to these rules (if it is possible):

if r_A < r_G, the guard moves r_G:  = r_G - 1

if r_G < r_A, the guard moves r_G:  = r_G + 1

Arthur can move to one of four adjacent cells (row up, row down, column left, column right). Both, Arthur and the guard can't move diagonally. Arthur and the guard move alternatively. The first move is made by Arthur. Arthur and the guard make the same number of moves. That is, if Arthur gets the amulet and he is caught during the next guard's move, then Arthur is killed. Given the description of the forest determine the minimal number of Arthur's steps needed to be made in order to reach the amulet of power.

The first line of each test case contains the number of rows N and the number of columns M in the matrix. (2 ≤ N, M ≤ 25)

The following N lines contains M characters. The j-th character on the i-th line describes the position (i, j) in the matrix.

'A' denotes the Arthur's initial position.

'G' denotes the guard's initial position.

'X' denotes the position occupied by dangerous animals.

'P' denotes the amulet of power.

'.' denotes other cells.

Output single integer R – the minimal numbers of steps needed to be made. If the amulet can not be reached or the Arhur will certainly be caught by the guard, output  - 1.

2 2
A.
GP

-1

2 3
A..
GXP

3

2 2
.G
AP

-1