E - Labyrint

Janke sa sníva, že je v bludisku. Nie, nenaháňa ju múmia ani nič také, zajtra má totiž skúšku a ešte nie je naučená. Jediný spôsob, ako sa zobudiť, je dostať sa z bludiska von, teda nájsť východ. A to čo najskôr!
Nie je to však obyčajné bludisko, toto je tvorené niekoľkými úrovňami, každé je zložené z políčok tvoriacich štvorčekovú mriežku.
Medzi úrovňami sa dá cestovať magickými portálmi. Každý portál má dva konce a dá sa použiť v oboch smeroch. Takéto cestovanie medzi dvoma políčkami trvá rovnako dlho ako vstup na susedné políčko.
Čas prechodu je totožný s počtom navštívených políčok(okrem políčka štart), pričom z každého políčka môžeme prejsť len na tie, s ktorými má spoločnú hranu. (a nie je to stena)
Vstup na políčko s portálom neznamená automaticky aj jeho použitie, to je dobrovoľné.

Janka hlavne potrebuje vedieť, kedy najskôr sa vie zobudiť. Ak to bude trvať veľmi dlho, nestihne sa všetko naučiť a môže rovno zabudnúť na tento termín, ostať snívať a bavkať sa s portálmi.

Úloha

Vytvorte program, ktorý načíta popis labyrintu a vypíše minimálny počet krokov potrebných na únik(resp. že sa to nedá)

Vstup

Prvý riadok vstupu obsahuje počet úrovní N (1≤N≤10). Nasleduje ich popis. Každá úroveň má na samostatnom riadku zadané rozmery R,S(1≤R,S≤20) a nasleduje R riadkov po S znakov reprezentujúcich jednotlivé políčka. Označenie políčok:

• . - voľné políčko
• # - stena
• + - Štart (len 1 pre celý vstup)
• = - Východ (len 1 pre celý vstup)
• A-Z - Políčko s portálom (každý použitý portál má práve 2 konce)

Výstup

Výstupom je minimálny počet krokov potrebný na to, aby sme sa dostali zo štartu k východu. Ak sa to nedá, výstup má byť -1.

Príklad

Vstup:

2
10 11
###########
#........+#
#.#########
#.#......B#
#....######
######....#
#A......#.#
######.##.#
#=........#
###########
7 8
########
#....#A#
#.##.#.#
#.#..#.#
#.#.##.#
#B#....#
########

Výstup:

53