#include <bits/stdc++.h>

using namespace std;

ifstream fin("barbar.in");
ofstream fout("barbar.out");

const int di[]={0,0,-1,1},dj[]={-1,1,0,0};
int n,m,a[1001][1001],h[1001][1001],si,sj,fi,fj;

struct dragon{
    int i,j,val;
};

queue<dragon>q;

bool ok(int i,int j){
    if(i<1||j<1||i>n||j>m) return false;
    return true;
}

queue<pair<int,int>>q2,gol;

bool lee(int att,int mij){
    q2.push({si,sj});
    int i,j;
    while(!q2.empty()){
        i=q2.front().first;
        j=q2.front().second;
        q2.pop();
        h[i][j]=att;
        if(i==fi&&j==fj){
            q2=gol;
            return true;
        }
        int ni,nj;
        for(int k=0;k<4;k++){
            ni=i+di[k];
            nj=j+dj[k];
            if(ok(ni,nj)){
                if(h[ni][nj]!=-1&&h[ni][nj]!=att&&a[ni][nj]>=mij){
                    q2.push({ni,nj});
                }
            }
        }
    }
    /**for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
           cout<<h[i][j]<<" ";
        }
        cout<<endl;
    }**/
    return false;
}

int main(){
    fin>>n>>m;
    char c;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            fin>>c;
            if(c=='I'){
                si=i;
                sj=j;
                a[i][j]=-1;
            }else if(c=='*'){
                a[i][j]=-1;
                h[i][j]=-1;
            }else if(c=='O'){
                fi=i;
                fj=j;
            }else if(c=='D'){
                a[i][j]=-1;
                h[i][j]=-1;
                dragon aux;
                aux.i=i;
                aux.j=j;
                aux.val=0;
                q.push(aux);
            }
        }
    }
    int st=1,dr=-1,rez=-1,mij,att=1;
    while(!q.empty()){
        int i=q.front().i,j=q.front().j,val=q.front().val;
        q.pop();
        if(a[i][j]!=-1) a[i][j]=val;
        int ni,nj;
        for(int k=0;k<4;k++){
            ni=i+di[k];
            nj=j+dj[k];
            if(ok(ni,nj)){
                if(a[ni][nj]==0){
                    dragon aux;
                    aux.i=ni;
                    aux.j=nj;
                    aux.val=val+1;
                    q.push(aux);
                    dr=max(dr,val+1);
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
           cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl<<endl<<endl;
    while(st<=dr){
        mij=(st+dr)/2;
        ///cout<<mij<<endl;
        bool ok;
        ok=lee(att,mij);
        att++;
        if(ok){
            if(rez==-1) rez=mij;
            else rez=min(rez,mij);
            st=mij+1;
        }else{
            dr=mij-1;
        }
    }
    fout<<rez;
    return 0;
}