Super Mario
Super Mario je jako nesretan. Zli Krokodil mu je oteo princezu. Ali! Super Mario planira napad. Ima Spijuna u dvorcu. On mu je dao mapu dvorca i uklonio sve prepreke osim zidova i alarma. Super Mario se iz svakog polja na mapi moze kretati gore, dolje, ljevo i desno. Zeli cim prije moguce doci do princeze i natrag kako mu se alarm nebi upalio. Recite mu za koliko minimalno vremena moze doc do princeze, osloboditi je i doci na pocetno mjesto ako mu za svaki pomak treba jedna sekunda i nemoze prolaziti kroz zidove.
InputPrvi redak prirodni brojevi R i S, broj redaka i stupaca u dvorcu. R, S <= 50.U sljedecih R redaka ima S znakova, to je mapa dvorca koju je nas junak Super Mario dobio od Spijuna. Znak M oznacava polje na kojem Super Mario krece i zavrsava (tocno jedno na mapi). Znak P oznacava polje na kojem se nalazi princeza (tocno jedn na mapi). Znak '.' oznacava prazno polje, a znak '#' zid.
OutputJedan broj koji oznacava za koliko sekundi Super Mario moze doci do princeze i natrag ili -1 ako nemoze doci do princeze.
Ulaz
Izlaz
5 5
M#P..
.###.
.#...
.#.##
.....Izlaz
28Ulaz
Izlaz
5 5
.#P..
.###.
.#...
.####
M....Izlaz
-1Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.