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!

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

$.$ celula libera
$*$ perete
$D$ dragon
$I$ punctul de plecare al lui Paftenie
$O$ iesirea din temnita

h2. Date de Iesire

h2. Exemplu

table(example). |_. barbar.in |_. barbar.out |_. Explicatie |

table(example). |_. barbar.in |_. barbar.out |

| 10 10
..........
.I....D...

..****....
...O......
..........

| 2
| O solutie posibila este urmatoarea :
..........
.I{*ooo*}.D...
....{*o*}.....
..D.{*o*}.D...
.*..{*oo*}....
D*...{*ooooo*}
{@*@}...D....{*o*}
..****...{*o*}
...O{*oooooo*}
.......... |

| 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/taskfooter" task_id="barbar")==

217