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. Deplasarea între două celule adiacente durează exact 1 secundă.

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.

Procurarea armei este instantă, având o durată de 0 secunde.

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
• Pentru 40% din teste, va exista un singur depozit de arme
• Se garantează că tărâmul poate fi apărat. Fiecare dwarf are cel puțin un depozit de arme și un turn de apărare la care poate ajunge

Exemplu

Explicație

În tărâm există un singur dwarf, care se află la poziția (2, 3). Acesta se va deplasa către depozitul de arme aflat la poziția (5, 5), își va lua o armă de acolo și își va continua deplasarea către turnul de la poziția (8, 8), parcurgând astfel o distanță egală cu 11.