#include <bits/stdc++.h>
using namespace std;
ifstream fin("barbar.in");
ofstream fout("barbar.out");
int n, m, mat[1001][1001], a[1001][1001];
int li, ci, lf, cf;
int ul, pr=1;
int dl[]={-1,0,1,0};
int dc[]={0,1,0,-1};

struct celula
{
   int x, y;
}v[1000001];

void Read()
{
    char c;
    fin >> n >> m;
    fin.get();
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            fin >> c;
            if(c == '.') mat[i][j]=0;
            else
                if(c == '*') mat[i][j] = -1;
            else
                if(c == 'D')
            {
                 mat[i][j] = -2;
                 v[++ul].x=i;
                 v[ul].y=j;
            }
            else if(c=='I') mat[i][j] = -3, li=i, ci=j;
            else mat[i][j] = -4, lf=i, cf=j;
        }
       fin.get();
    }
}

void Lee()
{
    int l, c, lv, cv;
    while(pr<=ul)
    {
        l = v[pr].x;
        c = v[pr].y;
        pr++;
        for(int i=0; i<4; i++)
        {
            lv = l + dl[i];
            cv = c + dc[i];
            if(lv>=1 && lv<=n && cv>=1 && cv<=m)
                if(mat[lv][cv]==0)
                {
                    if(mat[l][c] == -2)
                        mat[lv][cv] = 1;
                    else mat[lv][cv] = mat[l][c] + 1;
                    ul++;
                    v[ul].x = lv;
                    v[ul].y = cv;
                }
        }
    }
}

void Reinitializare()
{
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) a[i][j] = 0;
}

int Traseu(int x)
{
    int lv, cv, l, c;
    pr=ul=1;
    v[1].x = li;
    v[1].y = ci;
    while(pr<=ul)
    {
        l = v[pr].x;
        c = v[pr].y;
        pr++;
        for(int i=0; i<4; i++)
        {
            lv = l + dl[i];
            cv = c + dc[i];
            if(lv>=1 && lv<=n && cv>=1 && cv<=m)
               if((mat[lv][cv]>=x||mat[lv][cv]==-4)&&(mat[lv][cv]>0||mat[lv][cv]==-4)&&a[lv][cv]==0)
               { if(mat[lv][cv]==-4) return 1;
                 else {a[lv][cv]=1;ul++;v[ul].x = lv;v[ul].y = cv;}
               }
        }
    }
    Reinitializare();
    return 0;
}

int CB()
{
    int st, dr, mij, sol=-1;
    st = 1;
    dr = 3000;
    while(st<=dr)
    {
        mij = (st+dr)/2;
        if(Traseu(mij))
        {
            sol = mij;
            st = mij+1;
        }
        else dr = mij-1;
    }
    return sol;
}

int main()
{
    Read();
    Lee();
    fout << CB();



    return 0;
}

/*
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("barbar.in");
ofstream fout("barbar.out");
char c;
int xs,ys,xf,yf,n,m,a[1002][1002],b[1002][1002],cx[1000001],cy[1000001];
int pr,ul,s,d,mij;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
void LEE()
{ pr=1;int i,xc,yc,xv,yv;
    while(pr<=ul)
      { xc=cx[pr];
        yc=cy[pr];
         for(i=0;i<=3;i++)
          {xv=xc+dx[i];
           yv=yc+dy[i];
           if(xv>=1&&xv<=n&&yv>=1&&yv<=m)
             if(a[xv][yv]==0)
               { if(a[xc][yc]==-2) {a[xv][yv]=1;ul++;cx[ul]=xv;cy[ul]=yv;}
                 else {a[xv][yv]=a[xc][yc]+1;ul++;cx[ul]=xv;cy[ul]=yv;}
               }
          }
          pr++;
      }
}
int viz[1001][1001];
int le(int val)
{   pr=ul=1;int j,i,xc,yc,xv,yv;
   for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
     viz[i][j]=0;
    cx[pr]=xs;
    cy[pr]=ys;
    viz[xs][ys]=1;
    while(pr<=ul)
      { xc=cx[pr];
        yc=cy[pr];
         for(i=0;i<=3;i++)
          {xv=xc+dx[i];
           yv=yc+dy[i];
           if(xv>=1&&xv<=n&&yv>=1&&yv<=m)
             if((a[xv][yv]>=val||a[xv][yv]==-4)&&(a[xv][yv]>0||a[xv][yv]==-4)&&viz[xv][yv]==0)
               { if(a[xv][yv]==-4) return 1;
                 else {viz[xv][yv]=1;ul++;cx[ul]=xv;cy[ul]=yv;}
               }
          }
          pr++;
      }
     return 0;
}
int main()
{ fin>>n>>m;fin.get();
   int i,j;
   for(i=1;i<=n;i++)
     { for(j=1;j<=m;j++)
        { fin>>c;
           if(c=='.') a[i][j]=0;
           else if(c=='*') a[i][j]=-1;
           else if(c=='D') {a[i][j]=-2;ul++;cx[ul]=i;cy[ul]=j;}
           else if(c=='I') {a[i][j]=-3;xs=i;ys=j;}
           else if(c=='O') {a[i][j]=-4;xf=i;yf=j;}
        }
    fin.get();
     }
   LEE();

   s=1;d=n+m;
   while(s<=d)
    { mij=s+(d-s)/2;
      if(le(mij)==1) s=mij+1;
      else d=mij-1;
    }
 if((s-1)!=0) fout<<s-1;
 else fout<<-1;
    return 0;
}
*/