S - Sokoban

Sokoban (skladník) je logická hra, kde hráč posúva krabice v sklade a snaží sa ich umiestniť na vyznačené pozície. Sklad je 2D mapa znázorňujúca rozmiestnenie Sokobana, krabíc, stien a vyznačených pozícií. V jednom okamihu je možné posúvať iba jednu krabicu.

Úloha

Pre dané rozmiestnenie vecí v sklade nájdite najmenší počet krokov, ktorý potrebuje skladník urobiť, aby presunul jednu krabicu na jej vyznačené miesto.

Vstup

V prvom riadku súboru sa nachádzajú rozmery skladu N, M (1 ≤ N,M ≤ 20). Sklad je vždy ohraničený.

Nasleduje N riadkov s M znakmi.

Význam znakov:
# - stena
^ - krabica
$ - vyznačená (cieľová) pozícia
@ - skladník (Sokoban)
. - prázdne miesto

Výstup

Výstupom programu je minimálny počet krokov, ktoré musí skladník urobiť na presunutie krabice. Ak taká postupnosť krokov neexistuje, napíšte -1.

Príklad

Vstup:

8 8
..#####.
###...#.
#.^.#.##
#.#....#
#....#.#
####$..#
.#@..###
.#####..

Výstup:

34