//barbar3
#include<fstream.h>
int main()
{int r1,r2,s,c1,c2,a,j,i=1,lmax,n,n2,nd=0,lee1[1000001],lee2[1000001];  //00
char m[1001][1001];  //0
int  x,y,d[1001][1001],b[1001][1001];
ifstream q("barbar.in");
ofstream w("barbar.out");
q>>n>>n2;
for(i=1;i<=n;i++)
  {q>>m[i];
  for(j=1;j<=n2;j++)
    {d[i][j]=0;
    b[i][j]=0;
    if(m[i][j]=='D')
     {nd++;
     lee1[nd]=i;
     lee2[nd]=j;}
  if(m[i][j]=='I')
   {c1=i;
   c2=j;}
  if(m[i][j]=='O')
   {r1=i;
   r2=j;}}}
lmax=nd-1;
 d[lee1[1]][lee2[1]]=0;
 for(a=1;a<=lmax;a++)
   {i=lee1[a];
   j=lee2[a];
   if(i>1&&m[i-1][j]!='*'&&(d[i-1][j]==0||d[i-1][j]>d[i][j]+1))
    {d[i-1][j]=d[i][j]+1;
    lmax++;
    lee1[lmax]=i-1;
    lee2[lmax]=j;}
   if(j>1&&m[i][j-1]!='*'&&(d[i][j-1]==0||d[i][j-1]>d[i][j]+1))
    {d[i][j-1]=d[i][j]+1;
    lmax++;
    lee1[lmax]=i;
    lee2[lmax]=j-1;}
   if(i<n&&m[i+1][j]!='*'&&(d[i+1][j]==0||d[i+1][j]>d[i][j]+1))
    {d[i+1][j]=d[i][j]+1;
     lmax++;
    lee1[lmax]=i+1;
   lee2[lmax]=j;}
   if(j<n&&m[i][j+1]!='*'&&(d[i][j+1]==0||d[i][j+1]>d[i][j]+1))
    {d[i][j+1]=d[i][j]+1;
     lmax++;
     lee1[lmax]=i;
     lee2[lmax]=j+1;}}
lee1[1]=c1;
lee2[1]=c2;
int nr,in=1;
s=n;
while(in<s)
  {nr=in-1+((s-in+1)/2);
  lmax=1;
  for(x=1;x<=n;x++)
    for(y=1;x<=n2;x++)
      b[x][y]=0;
  for(a=1;a<=lmax;a++)
    {i=lee1[a];
    j=lee2[a];
    if(i>1&&(d[i-1][j]>=nr||d[i][j-1]==0)&&(m[i-1][j]=='.'||m[i][j+1]=='O')&&(b[i-1][j]==0||b[i-1][j]>b[i][j]+1))
     {b[i-1][j]=b[i][j]+1;
     lmax++;
     lee1[lmax]=i-1;
     lee2[lmax]=j;}
    if(j>1&&(d[i][j-1]>=nr||d[i][j-1]==0)&&(m[i][j-1]=='.'||m[i][j+1]=='O')&&(b[i][j-1]==0||b[i][j-1]>b[i][j]+1))
     {b[i][j-1]=b[i][j]+1;
     lmax++;
     lee1[lmax]=i;
     lee2[lmax]=j-1;}
    if(i<n&&(d[i+1][j]>=nr||d[i+1][j]==0)&&(m[i+1][j]=='.'||m[i][j+1]=='O')&&(b[i+1][j]==0||b[i+1][j]>b[i][j]+1))
     {b[i+1][j]=b[i][j]+1;
     lmax++;
     lee1[lmax]=i+1;
     lee2[lmax]=j;}
    if(j<n&&(d[i][j+1]>=nr||d[i][j+1]==0)&&(m[i][j+1]=='.'||m[i][j+1]=='O')&&(b[i][j+1]==0||b[i][j+1]>b[i][j]+1))
     {b[i][j+1]=b[i][j]+1;
     lmax++;
     lee1[lmax]=i;
     lee2[lmax]=j+1;}}
  if(b[r1][r2]!=0)
   {if(in==nr)
   in=nr+1;
   else
   in=nr;}
  if(b[r1][r2]==0)
   s=nr-1;}
if(in>s)
w<<s;
else
w<<in;
return 0;}