#include <bits/stdc++.h>

using namespace std;
const int MAX = 1005;
int n, m, st, dr, i, j, cnt, si, sj, ei, ej;
int temn[MAX][MAX], temnLee[MAX][MAX];

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
queue <int> dragY, dragX, x, y;
bool f = false;
bool OK(int i, int j){
    if(i<1 || j<1 || n<i || m<j){
        return false;
    }
    return true;
}

bool lee2(int h){
    f = false;
x.push(si);
y.push(sj);
    while(!x.empty()){
       i=x.front();
       j=y.front();
       x.pop();
       y.pop();
       for(int k=0;k<4;++k){
           int step_x=i+dx[k];
           int step_y=j+dy[k];
           if(h<=temn[step_x][step_y] && OK(step_x,step_y)==1){
               x.push(step_x);
               y.push(step_y);
               if(step_x == ei && step_y == ej){
                   return true;
                   
               }
           }
       }
      
    }
}

void lee1(){

    i = 1;
    
     while(!dragX.empty() && !dragY.empty()){
         i = dragX.front();
         j = dragY.front();
         dragX.pop();
        dragY.pop();
       for(int k=0;k<4;++k){
           int step_x=i+dx[k];
           int step_y=j+dy[k];
      
           if(temn[step_x][step_y]==0 && OK(step_x,step_y)==1){
               if(temn[i][j] == -2){
                   temn[step_x][step_y]=temn[i][j]+3;
               } else {
               temn[step_x][step_y]=temn[i][j]+1;
             
               }
               dragX.push(step_x);
               dragY.push(step_y);
           }
       }
       i++;
    }

}



int main()
{
    int i=1, mid, st1, dr1, Min = MAX+1;
    char c;
    cin >> n >> m;
    for(int a=1;a<=n;a++){
        for(int b=1;b<=m;b++){
            cin >> c;
            if(c=='.'){
                temn[a][b] = 0;
                i++;
            } else if(c=='*'){
                temn[a][b] = -1;
            } else if(c=='D'){
                temn[a][b] = -2;
                dragY.push(b);
                dragX.push(a);
                i++;
            } else if(c=='I'){
                si = a;
                sj = b;
            } else if(c=='O'){
                ei = a;
                ej = b;
            }
        }
    }
    lee1();
   for(int a=1;a<=n;a++){
        for(int b=1;b<=m;b++){
            cout << temn[a][b] << " ";
        }
        cout << "\n";
   }
   st = 1;
   dr = max(n, m);
   while(st<dr){
      mid = (dr+st)/2;
    
      if(lee2(mid)){
          if(Min>mid){
              Min = mid;
          }
          st = mid+1;
          dr = dr;
      } else if (!lee2(mid)){
          st = st;
          dr = mid-1;
      }
   }
   cout << Min;
}