==Include(page="template/taskheader" task_id="barbar")==

==Include(page="template/taskheader" task_id="barbar")==
 
Paftenie barbarul este un renumit aventurier. A condus razboaie, a descoperit comori, a cucerit cetati si inimile domnitelor. Insa de aceasta data a fost capturat de catre dusmanii sai cei mai temuti si aruncat intr-o temnita. Temnita este de fapt un grid de dimensiune {$R*C$}. In anumite celule exista dragoni, unele sunt ocupate de pereti, iar altele sunt libere. Paftenie trebuie sa iasa din temnita mergand numai prin celule libere (o celula are maxim 4 vecini) , si asta stand cat mai departe de fiorosii dragoni ale caror flacari ii pot deteriora vestimentatia (astfel incat minima din distantele pana la cel mai apropiat dragon din fiecare din celulele traseului sau sa fie maxim).
 
h2. Cerinta
 
Ajutati-l pe barbarul Paftenie sa iasa din temnita, determinand un traseu astfel incat distanta minima pana la cel mai apropiat dragon din fiecare dintre celulele traseului sau sa fie maxima!
 
h2. Date de Intrare
 
Pe prima linie a fisierului de intrare $barbar.in$ sunt date doua numere intregi $R$ si {$C$}, reprezentand numarul liniilor, respectiv al coloanelor temnitei. Pe urmatoarele $R$ linii se afla cate $C$ caractere, neseparate prin spatii, cu urmatoarele semnificatii:
$.$ celula libera
$*$ perete
$D$ dragon
$I$ punctul de plecare al lui Paftenie
$O$ iesirea din temnita
 
h2. Date de Iesire
 
Fisierul de iesire $barbar.out$ va contine pe prima linie un singur numar, reprezentand valoarea maxima pentru minima din distantele pana la cel mai apropiat dragon din fiecare din celulele traseului. In caz ca nu exista solutie se va afisa {$-1$}.
 
h2. Restrictii si precizari
 
* $1 ≤ R, C ≤ 1.000$
* Se garanteaza ca in temnita exista cel putin un dragon
 
h2. Exemplu
 
table(example). |_. barbar.in |_. barbar.out |
| 10 10
..........
.I....D...
..........
..D...D...
.*........
D*........
*...D.....
..****....
...O......
..........
| 2 |
 
h3. Explicatii
 
O solutie posibila:
$..........$
$.I{*ooo*}.D...$
$....{*o*}.....$
$..D.{*o*}.D...$
$.*..{*oo*}....$
$D*...{*ooooo*}$
${@*@}...D....{*o*}$
$..****...{*o*}$
$...O{*oooooo*}$
$..........$
 
 
==Include(page="template/taskfooter" task_id="barbar")==
 
 

==Include(page="template/raw")==
 
barbar
 
 
 
Paftenie barbarul este un renumit aventurier. A condus razboaie, a descoperit comori, a cucerit cetati si inimile domnitelor. Insa de aceasta data a fost capturat de catre dusmanii sai cei mai temuti si aruncat intr-o temnita. Temnita este de fapt un grid de dimensiune R*C. In anumite celule exista dragoni, unele sunt ocupate de pereti, iar altele sunt libere. Paftenie trebuie sa iasa din temnita mergand numai prin celule libere (o celula are maxim 4 vecini) , si asta stand cat mai departe de fiorosii dragoni ale caror flacari ii pot deteriora vestimentatia (astfel incat minima din distantele pana la cel mai apropiat dragon din fiecare din celulele traseului sau sa fie maxim).
 
h2. Cerinta
 
Ajutati-l pe barbarul Paftenie sa iasa din temnita, determinand un traseu astfel incat minima din distantele pana la cel mai apropiat dragon din fiecare din celulele traseului sau sa fie maxim!
 
h2. Date de Intrare (fisier: barbar.in)
 
Pe prima linie a fisierului de intrare sunt date doua numere intregi R si C, reprezentand numarul liniilor, respectiv al coloanelor temnitei. Pe urmatoarele R linii se afla cate C caractere, neseparate prin spatii, cu urmatoarele semnificatii:
 
. celula libera
 
* perete
 
D dragon
 
I punctul de plecare al lui Paftenie
 
O iesirea din temnita
 
h2. Date de Iesire (fisier: barbar.out)
 
Fisierul de iesire va contine pe prima linie un singur numar, reprezentand valoarea maxima pentru minima din distantele pana la cel mai apropiat dragon din fiecare din celulele traseului. In caz ca nu exista solutie se va afisa "-1".
 
h2. Restrictii si precizari
 
* 1 <= R, C <= 1.000
 
* Se garanteaza ca in temnita exista cel putin un dragon
 
h2. Exemplu
 
barbar.in barbar.out Explicatie
10 10 2 O solutie posibila este urmatoarea :
.......... ..........
.I....D... .Iooo.D...
.......... ....o.....
..D...D... ..D.o.D...
.*........ .*..oo....
D*........ D*...ooooo
*...D..... *...D....o
..****.... ..****...o
...O...... ...Ooooooo
.......... ..........
 
 
==Include(page="template/taskfooter" task_id="barbar")==

217