Problema: Mewtwo / 
Autor: Cerința
Ash este un antrenor Pokemon ambițios, setându-și scopul să devină cel mai bun. Din păcate, rivalul său, Gary, a furat startul și are Pokemoni mai puternici decât cei ai lui Ash.
Totuși, Ash nu se va da bătut chiar așa ușor! Are un plan de bătaie: în aventurile sale a găsit o clădire misterioasă care poate fi reprezentată ca o matrice de N x M, fiecare celulă reprezentând conținutul unei camere. În această clădire se află:
- Ash (codificat cu
A): Ash se află inițial în această cameră - Mewtwo (codificat cu
M): cel mai puternic Pokemon cunoscut de om. Ash are deja un Master Ball, așa că îl va poate prinde pe Mewtwo cu ușurință. - Gary (codificat cu
G): a fost provocat de Ash la o bătălie de Pokemoni și îl așteaptă într-o anumită cameră - cameră liberă (codificată cu
_): Ash poate accesa această cameră - cameră ocupată (codificată cu
#): Ash nu poate accesa această cameră
Planul său constă în a-l prinde pe Mewtwo, după aceea în a-l confrunta pe Gary. Ash se poate deplasa în cele patru direcții cardinale (N, E, S, V). Știind că o deplasare se face într-o secundă, determinați numărul minim de secunde în care Ash poate ajunge la Mewtwo, apoi la Gary.
Date de intrare
Programul citește de la tastatură numerele N și M, reprezentând dimensiunile clădirii misterioase.
Pe următoarele N linii se vor afla șiruri de câte M caractere, reprezentând structura clădirii.
Date de ieșire
Se va afișa numărul minim de secunde în care Ash poate ajunge la Mewtwo, apoi la Gary.
Restricții și precizări
- Când zicem cel mai puternic Pokemon, ne referim comparativ cu cei din generația
1. - Se garantează că Ash își va putea executa planul de bătaie
1 ≤ N ≤ 1.0001 ≤ M ≤ 1.000
Exemplu:
Intrare
8 10 __#_______ _A#_______ __#___M_#_ __#__####_ __##_##___ _____#__G_ __#__#____ __########
Ieșire
21
Explicație
Distanța minimă de la Ash până la Mewtwo este 12, iar distanța minimă de la Mewtwo panâ la Gary este 9. Suma acestor distante este 21.
