# 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;
}