Ammo X11353


Statement
 

pdf   zip

html

Neo has run out of ammo and quickly needs to find some more. To reach the ammo depot Neo might need to traverse two different dimensions of the Matrix. Help Neo find the shortest path to the ammo depot.

Input

The input consists of several test cases. Each test case starts with the number of rows 1≤ n≤ 100 and the number of columns 1≤ m≤ 100 of the Matrix. This is followed by 2n rows with m characters each, corresponding to two different dimensions of the Matrix. The character "." is a free cell of the Matrix, "#" is a blocked cell, "P" is a portal that allows Neo to move to the opposite dimension, "N" is Neo’s starting position, and "A" is the ammo depot.

Output

For each test case, a number on a single line representing the minimum distance to the ammo depot, or −1 in case Neo cannot reach the ammo depot.

Public test cases

  • Input

    2 3
N#.
P#A
..P
...

    Output

    7

  • Input

    2 3
N..
..P
.A.
...

    Output

    6

  • Input

    3 3
...
.##
..A
P#.
.#P
..N

    Output

    9
    • Information
    Author
    Anders Jonsson
    Language
    English
    Official solutions
    Unknown.
    User solutions
    C++