== include(page="template/taskheader" task_id="dwarfland") ==
Poveste și cerință...
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ă.
h2. 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.
h2. Date de intrare
Fișierul de intrare $dwarfland.in$ ...
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ț.
h2. Date de ieșire
În fișierul de ieșire $dwarfland.out$ ...
În fișierul de ieșire $dwarfland.out$ se va afla un singur număr natural, timpul minim necesar pregătirii pentru asediu.
h2. Restricții
* $... ≤ ... ≤ ...$
* $1 ≤ M, N ≤ 1.000$
* Pentru 30% 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
h2. Exemplu
table(example).
|_. dwarfland.in |_. dwarfland.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 10 10
.A........
..D.......
..........
..........
....A.....
..........
..........
.......T..
..........
..........
| 11
|
h3. 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$].
== include(page="template/taskfooter" task_id="dwarfland") ==
