U3t - Hľadanie pokladu (ťažký)

Časový limit: 2s, Pamäťový limit: 64MiB

Programovací jazyk: Java

Počet bodov: 4

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Jožko nedávno vyhral v kartách mapu piráta Jonatána. Keďže už lokalizoval ostrov, rozhodol sa, že sa naň dostane zoskokom padákom z lietadla. Lenže nie všetko sa vydarilo tak ako si plánoval. Na ostrove Jožko síce pristál, no jeho plavecká výstroj, taktiež zhodená z lietadla, dopadla úplne inde ako on. A aby toho nebolo málo, tak na ostrove sú rôzne skalnaté plochy, cez ktoré prejsť nevie, jazerá cez ktoré vie preplávať len ak má svoju výstroj. Našťastie, Jožko je talentovaný matematik a kým pristával, stihol si vypočítať kam dopadne jeho výstroj a po dopade na ostrov si to aj zaznačil do svojej mapy. Teraz však rozmýšľa, ako sa najrýchlejšie dostane k pokladu. Pomôžte mu.

Úloha

Daná je mapa ostrova. Vypíšte najkratší čas za ktorý sa dá k pokladu dostať, alebo správu, že sa to nedá. Pohybovať sa dá do štyroch smerov – hore, dole, vpravo, vľavo. Pohyb z jedného políčka na druhé trvá jednu jednotku času. V tejto úlohe ešte predpokladajme, že plavecká výstroj sa považuje za zobratú po prejdení políčkom, na ktorom je. Po jej zobratí sa už dá prechádzať aj cez vodu. Okolo celého ostrova sa ešte nachádza voda, čiže plávať sa dá aj mimo mapy.

Vstup

V prvom riadku sú dve čísla N a M určujúce veľkosť ostrova. Ďalej nasleduje N riadkov, každý z nich obsahuje M znakov. Znaky sú buď:

‘.’ - zem, dá sa chodiť suchou nohou (bez výstroja)
‘~’ - voda, cez toto územie sa dá prejsť len s plaveckým výstrojom
‘#’ - skala, toto políčko je nedostupné
‘@’ - políčko na ktorom je výstroj
‘X’ - reprezentuje tvoju začiatočnú pozíciu
‘P’ - poklad

Vstup obsahuje presne jedno políčko 'P', presne jedno políčko 'X' a presne jedno políčko '@'.

Výstup

Výstupom je jedno číslo - najkratší čas, za ktorý sa dá dostať k pokladu alebo reťazec „impossible“ (bez úvodzoviek), ak sa k pokladu nedá nijako dostať.

D1

1≤N≤50, 1≤M≤50

D2

1≤N≤1000, 1≤M≤1000

Príklad 1

Vstup

3 3
X@.
~~.
P..

Výstup:

Vysvetlenie: Najprv prejdeme na políčko so znakom @ (výstroj). Potom už len preplávame cez vodu na druhú stranu. Zaberie nám to 4 jednotky času.

Príklad 2

Vstup

9 9
~~##P##~~
~~~######
####.X..#
.@..#.#.#
....#.#..
....#.###
..###.###
......#~~
######.~~

Výstup

Vysvetlenie: Kedže teraz sa k pokladu nedá dostať suchou nohou, musíme zobrať výstroj, a potom preplávame po mori k pokladu.

Príklad 3

Vstup

7 7
X...#@#
.~~~~~#
.~~~~~.
.~~P~~.
.~~~~~.
.~~~~~.
.......

Výstup

impossible

Vysvetlenie: Poklad je uprostred jazera, no k výstroju sa nedá nijako dostať.

Príklad 4

Vstup

7 5
X#..~
.#..~
.#.##
....@
~~~~.
~~~##
~~..P

Výstup

Úloha je prevzatá zo súťaže PALMA.

PAZ1b 3. sada