# include <stdio.h>
# include <stdlib.h>
const int MAXD=1000; //AICI!!! 1000
typedef struct NODD {int i,j;NODD *next;};
typedef struct NOD {int i,j,val;};
typedef NOD HEAP[MAXD*MAXD+1];
const int vi[5]={0,-1,0,1,0},vj[5]={0,0,1,0,-1};
const int PERETE=3*MAXD;
int a[MAXD+1][MAXD+1],n,m,d[MAXD+1][MAXD+1],pafi,pafj,exiti,exitj;
NODD *prim,*ultim;
void citire()
{
NODD *p;int i,j;
char s[2*MAXD];
FILE *f=fopen("barbar.in","r");
fscanf(f,"%d%d",&n,&m);
fgets(s,2*MAXD,f);
for (i=1;i<=n;i++)
{
fgets(s+1,2*MAXD,f);
for (j=1;j<=m;j++)
{
if (s[j]=='*') a[i][j]=-1;
if (s[j]=='D')
{
p=(NODD*) malloc (sizeof(NODD));
(*p).i=i;(*p).j=j;(*p).next=NULL;(*ultim).next=p;
ultim=p;
d[i][j]=0;
a[i][j]=-2;
}
if (s[j]=='I')
{
pafi=i;pafj=j;
}
if (s[j]=='O')
{
exiti=i;exitj=j;
}
}
}
fcloseall();
}
void BFS_DRAGONI (NODD *prim, NODD *ultim)
{
NODD *p;int dir,inou,jnou;
while (prim)
{
for (dir=1;dir<=4;dir++)
{
inou=(*prim).i+vi[dir];jnou=(*prim).j+vj[dir];
if (a[inou][jnou]!=-1&&a[inou][jnou]!=-2&&d[inou][jnou]==0&&inou<=n&&inou>0&&jnou<=m&&jnou>0)
{
p=(NODD*) malloc (sizeof(NODD));
(*p).i=inou;(*p).j=jnou;(*p).next=NULL;(*ultim).next=p;
d[inou][jnou]=d[(*prim).i][(*prim).j]+1;
ultim=p;
}
}
p=prim;
prim=(*prim).next;
free(p);
}
}
void scrie(int sol)
{
FILE *g=fopen("barbar.out","w");
fprintf(g,"%d\n",sol);
fcloseall();
}
void scufunda_heap(HEAP &c, int heaplen)
{
int poz=1,max,aux;
while (2*poz<=heaplen)
{
max=poz;
if (c[2*poz].val>c[max].val) max=2*poz;
if (2*poz+1<=heaplen&&c[2*poz+1].val>c[max].val) max=2*poz+1;
if (max==poz) break;
else
{
aux=c[poz].i;c[poz].i=c[max].i;c[max].i=aux;
aux=c[poz].j;c[poz].j=c[max].j;c[max].j=aux;
aux=c[poz].val;c[poz].val=c[max].val;c[max].val=aux;
poz=max;
}
}
}
void ridica_heap(HEAP &c, int heaplen)
{
int poz=heaplen,aux,tata=heaplen/2;
while (tata)
if (c[poz].val>c[tata].val)
{
aux=c[poz].i;c[poz].i=c[tata].i;c[tata].i=aux;
aux=c[poz].j;c[poz].j=c[tata].j;c[tata].j=aux;
aux=c[poz].val;c[poz].val=c[tata].val;c[tata].val=aux;
poz=tata;tata=poz/2;
}
else break;
}
int BFS_PAFTEMIE()
{
int i,j,dir,inou,jnou;long int heaplen;
//1. parcurgem a[][] ca sa eliminam posibilele valori -2
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
if (a[i][j]==-2) a[i][j]=0;
else if (a[i][j]==-1) a[i][j]=PERETE;
//2. cream coada si incarcam in coada pozitia initiala a lui Paftemie
HEAP coada;
coada[1].i=pafi;coada[1].j=pafj;coada[1].val=d[coada[1].i][coada[1].j];heaplen=1;
while (heaplen>0&&d[coada[1].i][coada[1].j]>=0)
{
a[coada[1].i][coada[1].j]=coada[1].val;
if (coada[1].i==exiti&&coada[1].j==exitj) return coada[1].val;
if (a[coada[1].i][coada[1].j]==0) a[coada[1].i][coada[1].j]=PERETE;
for (dir=1;dir<=4;dir++)
{
inou=coada[1].i+vi[dir];jnou=coada[1].j+vj[dir];
if (inou>0&&inou<=n&&jnou>0&&jnou<=m&&a[inou][jnou]==0)
{
coada[++heaplen].i=inou;coada[heaplen].j=jnou;
if (d[inou][jnou]<coada[1].val) coada[heaplen].val=d[inou][jnou];
else coada[heaplen].val=coada[1].val;
a[coada[heaplen].i][coada[heaplen].j]=-coada[heaplen].val;
ridica_heap(coada,heaplen);
}
}
coada[1].i=coada[heaplen].i;coada[1].j=coada[heaplen].j;coada[1].val=coada[heaplen].val;
heaplen--;
scufunda_heap(coada, heaplen);
}
//. daca nu exista saolutie, se va afisa -1
return -1;
}
int main()
{
//1. pentru optimizare, vom aloca coada pentru dragoni din main, prin intermediul functiei de citire.
ultim=(NODD*) malloc (sizeof(NODD)); prim=ultim;
citire();prim=(*prim).next;
//2. facem BFS-ul pentru dragoni -> se va vedea efectul in matricea d[][]
BFS_DRAGONI(prim,ultim);
//3. vom efectua BFS pentru Paftemie -> se va vedea efectul in matricea a[][]
int sol=BFS_PAFTEMIE();
//4. vom scrie solutia;
scrie(sol);fcloseall();
return 0;
}