Diferențe pentru problema/dwarfland între reviziile #4 si #12

== include(page="template/taskheader" task_id="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:

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

* $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.

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.

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

h2. 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.

* 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") ==