Finále

E: Hořící les

Abys mohl odevzdávat úlohy, musíš se přihlásit nebo zaregistrovat

Nejsi finalista, takže se neobjevíš ve výsledcích.

Zadání (Řešení)

Hoří les! Dobrovolný hasič Tonda je rád, protože konečně může pomoct hasit. Je to jeho první požár v životě, proti kterému bude bojovat. Už se nemůže dočkat, až doběhne do hasičárny a přihlásí se do služby.

Předtím ale musí vyřešit dva problémy. Zaprvé, najít doma všechno svoje vybavení, tedy obě boty, kalhoty, blůzu, hasičskou helmu a rukavice. A zadruhé, doběhnout do hasičárny. Nejkratší cesta do ní z jeho domu ale vede lesem. A tam hoří.

Les je pro nás obdélníková mřížka, na které některá políčka hoří (jsou zadána jako #). Některá políčka nehoří, dá se jimi procházet, ale začnou hořet, až se k nim dostane oheň (nehořící políčka jsou zadána jako .), a potom budou hořet donekonečna. Oheň se šíří do čtyř směrů: nahoru, doprava, dolů a doleva. Na některých políčkách je zase skála (@), ta políčka nikdy nezačnou hořet, oheň se přes ně nedostane, ale Tonda taky ne.

Tonda začíná v čase 0 kdekoliv na levém okraji lesa, tedy na libovolném řádku v prvním sloupečku označeném .. Oheň se šíří rychlostí jedno políčko za minutu, stejně rychle se může pohybovat i Tonda. Tonda může vstupovat jenom na nehořící políčka, na kterých není skála. Má za úkol dostat se do libovolného řádku posledního sloupečku lesa. Tam už bude v bezpečí.

Jak dlouho ještě může Tonda hledat svoje věci, aby pak jako hrdina proběhl lesem (nejlíp s plameny těsně za zády) a přidal se k hasičům? Vypište nejpozdější čas, kdy může vyrazit, aby se ještě dostal na druhý konec lesa. Pokud se tam nemůže dostat ani na začátku, vypište -1. Pokud nikdy nezačne hořet celý les a vždy se jím bude dát projít, vypište inf.

Tvar vstupu

Na prvním řádku vstupního souboru máte zadáno T, počet testovacích vstupů. Každý vstup vypadá následovně:

Na prvním řádku jsou dvě čísla R a S, to znamená, že les má R řádků a S sloupců. Na dalších R řádcích je vždy S znaků tvořících les, a to

  • .   nehořící políčko, kterým se dá procházet
  • #   oheň
  • @   skála

Máte zaručeno, že v prvním sloupci je alespoň jednou ..

Tvar výstupu

Pro každý vstup vypište na zvláštní řádek jedno číslo, čas, kdy se dá nejpozději proběhnout lesem.

Lehká verze

  • T ≤ 20
  • 1 ≤ R,S ≤ 200

Těžká verze

  • T ≤ 20
  • 1 ≤ R,S ≤ 1 001

Ukázkový výstup

4
5 10
...@.@...#
.......#..
...@@@@@@@
...@......
......@..@
2 2
#.
..
2 4
.#@.
..@.
2 3
...
@@.

Ukázkový výstup

5
0
-1
inf

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)