P - PivnicaČasový limit: 2s, Pamäťový limit: 64MiBProgramovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3Počet bodov: 1 [ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ] Laco si minulú jeseň odložil kosačku do pivnice do kúta, aby mu nezavadzala. Do pivnice potom odkladal množstvo iných vecí na rôzne miesta. Teraz, keď už zase vyrástla vysoká tráva by ju potreboval dostať von - najlepšie tak, aby ostatné veci nemusel vyberať ani presúvať. Kosačka má však dlhú rúčku, ktorá jej bráni v pohybe. Otáčať na mieste sa môže na každej pozícii (so sklopenou rúčkou), ale pohybovať sa môže len ak je dosť miesta pre rúčku za kosačkou. Spočítajte dĺžku najkratšej cesty kosačky von z pivnice pre dané rozmiestnenie vecí v pivnici. Pivnicu ju možné reprezentovať ako obdĺžnik s políčkami. Kosačka sa teda môže posúvať iba v prípade, že je za ňou voľné políčko. Výnimkou sú okraje, ktoré majú políčka väčších rozmerov, a teda na okraji je tiež možné posunúť kosačku. Kosačka je na ľavom hornom okraji a vchod do pivnice v pravom dolnom okraji.ÚlohaPre dané rozmiestnenie vecí v pivnici nájdite najkratšiu cestu ako vybrať kosačku von. VstupV prvom riadku súboru sa nachádzajú rozmery pivnice N, M. Nasleduje N riadkov s M znakmi, pričom znak # znamená obsadenú pozíciu a znak . prázdne miesto.
1 ≤ M,N ≤ 300 VýstupVýstupom programu je dĺžka najkratšej cesty kosačky von z pivnice. Ak taká cesta neexistuje, napíšte -1. PríkladVstup:10 10 .######.## .#......## .##.###.## .##.###.## .##.###.## .##.###.## .##.....## .##.###.## .##.###.## ....##.... Výstup:34 |