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

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

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

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.

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.

h2. Date de intrare

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

* Pe tărâm va exista cel puțin un dwarf, un depozit de arme și un turn de apărare
* Pentru 40% din teste, va exista un singur depozit de arme

h2. Exemplu
table(example).
|_. dwarfland.in |_. dwarfland.out |

| 10 10
.A........
..D.......
..........
..........
....A.....
..........
..........
.......T..
..........
..........
| 11

| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.

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