#include <iostream>
#include <fstream>
#include <deque>
using namespace std;

int dx[]={-1, 1, 0, 0};
int dy[]={0, 0, -1, 1};
char mat[1004][1004];
int r, c;
int distanta[1004][1004];

struct Vizitat {
    bool x1:1;
};

struct Optim {
    bool x1:1;
    bool x2:1;
    bool x3:1;
    bool x4:1;
    bool x5:1;
    bool x6:1;
    bool x7:1;
    bool x8:1;
    bool x9:1;
    bool x10:1;
    bool x11:1;
    bool x12:1;
} viz[1004][1004];

int transformare(Optim a) {
     int x;
     x=(1<<11)*a.x1 + (1<<10)*a.x2 + (1<<9)*a.x3 + (1<<8)*a.x4 + (1<<7)*a.x5 + (1<<6)*a.x6 +
       (1<<5)*a.x7 + (1<<4)*a.x8 + (1<<3)*a.x9 + (1<<2)*a.x10 + 2*a.x11 + a.x12;
     return x;
}

void stabilire(int nr, int x, int y) {
     int p, q;
     p=nr%2; nr=nr/2;
     viz[x][y].x12=p;
     p=nr%2; nr=nr/2;
     viz[x][y].x11=p;
     p=nr%2; nr=nr/2;
     viz[x][y].x10=p;
     p=nr%2; nr=nr/2;
     viz[x][y].x9=p;
     p=nr%2; nr=nr/2;
     viz[x][y].x8=p;
     p=nr%2; nr=nr/2;
     viz[x][y].x7=p;
     p=nr%2; nr=nr/2;
     viz[x][y].x6=p;
     p=nr%2; nr=nr/2;
     viz[x][y].x5=p;
     p=nr%2; nr=nr/2;
     viz[x][y].x4=p;
     p=nr%2; nr=nr/2;
     viz[x][y].x3=p;
     p=nr%2; nr=nr/2;
     viz[x][y].x2=p;
     p=nr%2; nr=nr/2;
     viz[x][y].x1=p;
}

void BFSdragon(int startx, int starty) {
    int mini=1000000, i, d=10000, x, p, q, y, dragon=0, fast;
    deque<pair<int, int> > deq;
    for(x=1; x<=r; x++) {
         for(y=1; y<=c; y++) {
              viz[x][y].x1=0; viz[x][y].x2=0; viz[x][y].x3=0; viz[x][y].x4=0; viz[x][y].x5=0; viz[x][y].x6=0;
              viz[x][y].x7=0; viz[x][y].x8=0; viz[x][y].x9=0; viz[x][y].x10=0; viz[x][y].x11=0; viz[x][y].x12=0;
         }
    }
    deq.push_back(make_pair(startx, starty));
    viz[startx][starty].x12=1;
    while(!deq.empty()) {
         p=deq.front().first;
         q=deq.front().second;
         for(i=0; i<4; i++) {
              x=p+dx[i];
              y=q+dy[i];
              if(transformare(viz[x][y])==0 && (mat[x][y]=='I' || mat[x][y]=='D' || mat[x][y]=='.' || mat[x][y]=='O')) {
                   fast=transformare(viz[p][q]);
                   stabilire(fast+1, x, y);
                   if(fast<distanta[x][y]) {
                        distanta[x][y]=fast;
                   }
                   if(mat[x][y]=='D') {
                        distanta[x][y]=0;
                   }
                   deq.push_back(make_pair(x, y));
              }
         }
         deq.pop_front();
    }      
}

int BFS(int startx, int starty, int endx, int endy, int dist) {
    //dist = distanta minima pina la dragon ( > )
    deque<pair<int, int> > Q;
    int ok=0, i, j, d, x, y, p, q, mini;
    Vizitat viz[1004][1004];
    for(i=1; i<=r; i++) {
         for(j=1; j<=c; j++) {
              viz[i][j].x1=false;
         }
    }
    //verificare
    mini=distanta[startx][starty];
    if(mini<dist) { return 0; }
    viz[startx][starty].x1=true;
    Q.push_back(make_pair(startx, starty));
    while(!Q.empty()) {
         x=Q.front().first;
         y=Q.front().second;
         for(i=0; i<4; i++) {
              ok=0;
              p=x+dx[i];
              q=y+dy[i];
              //mini=BFSdragon(p, q);
              mini=distanta[p][q];
              if(mini<dist) { ok=1; }
              if(ok==0 && viz[p][q].x1==false && (mat[p][q]=='I' || mat[p][q]=='D' || mat[p][q]=='.' || mat[p][q]=='O')) {
                   if(p==endx && q==endy) {
                        return 1;
                   }
                   viz[p][q].x1=true;
                   Q.push_back(make_pair(p, q));   
              }
         }
         Q.pop_front();
    }                
    return 0;
}


int cautabinar(int startx, int starty, int endx, int endy, int st, int dr) {
    int mij, q;
    while(st<=dr) {
        mij=st+(dr-st)/2;
        q=BFS(startx, starty, endx, endy, mij);
        if(q==0) { dr=mij-1; }
        else {
             if(BFS(startx, starty, endx, endy, mij+1)==1) { 
                  st=mij+1; 
             }
             else { return mij; }
        }
    }
    return -1;
}


int main() {
    fstream f2;
    FILE *f1=fopen("barbar.in", "r");
    int i, j, k, p, startx, starty, endx, endy;
    int drx[1001], dry[1001], nrd=0;
    //r linii, c coloane
    //f1.open("barbar.in", ios::in);
    fscanf(f1, "%d %d\n",&r,&c);
    for(i=0; i<=r; i++) {
         mat[0][i]='X'; mat[c+1][i]='X';
    }
    for(i=0; i<=c; i++) {
         mat[i][0]='X'; mat[i][r+1]='X';
    }
    mat[r+1][c+1]='X';
    for(i=1; i<=r; i++) {
         for(j=1; j<=c; j++) {
              distanta[i][j]=99999;
              fscanf(f1, "%c ",&mat[i][j]);
              fscanf(f1, "\n");
              //f1>>mat[i][j];
              if(mat[i][j]=='I') { startx=i; starty=j; }
              if(mat[i][j]=='O') { endx=i; endy=j; }
              if(mat[i][j]=='D') {
                   drx[nrd]=i; dry[nrd]=j;
                   nrd++;
                   //BFSdragon(i, j); 
              }
         }
    }
    for(i=0; i<nrd; i++) {
         BFSdragon(drx[i], dry[i]);
    }
    f2.open("barbar.out", ios::out);
    f2<<cautabinar(startx, starty, endx, endy, 0, 500)<<endl;
    /**
    int bl=0,br=r*c,bm;
    while (br-bl>1)
    {
        bm=(bl+br)>>1;
        if (BFS(startx, starty, endx, endy, bm)) bl=bm;
        else br=bm;
    }
    if (bl) fprintf(out, "%d\n",bl);
    else 
     if(BFS(startx, starty, endx, endy, 0)) { fprintf(out, "0\n"); }
     else { fprintf(out, "-1\n"); }
    **/
    fclose(f1); f2.close();
    return 0;
}