Fișierul intrare/ieșire	dwarfland.in, dwarfland.out	Sursă	Concurs clasic
Autor	Teodor Plop	Adăugată de	Teodor Plop • teodor94
Timp de execuție pe test	0.15 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	3.5

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Dwarfland

Tărâmul dwarfilor este format din M * N celule distribuite într-o formă dreptunghiulară, M linii și N coloane. Celulele pot fi de mai multe tipuri:

• . – celulă liberă
• D – celulă în care se află un dwarf
• Z – celulă de tip zid, inaccesibilă
• A – celulă în care se află un depozit de arme
• T – celulă în care se află un turn de apărare

Dwarfii se pot deplasa în oricare din cele 4 direcții: N, S, E, V. Singurele celule inaccesibile sunt cele de tip zid.

Cerință

Tărâmul dwarfilor este sub asediu iar dwarfii trebuie să îl apere. Pentru a-l apăra, fiecare dwarf se va deplasa către un depozit de arme, își va procura o armă de acolo și se va deplasa mai apoi către un turn de apărare. Să se calculeze timpul minim necesar pregătirii pentru asediu.

Date de intrare

Fișierul de intrare dwarfland.in conține pe prima linie numerele naturale M și N, iar pe următoarele M linii câte N caractere, având semnificația din enunț.

Date de ieșire

În fișierul de ieșire dwarfland.out se va afla un singur număr natural, timpul minim necesar pregătirii pentru asediu.

Restricții

• 1 ≤ M, N ≤ 1.000
• Pe tărâm va exista cel puțin un depozit de arme și un turn de apărare.

Exemplu

Explicație

...