#include <bits/stdc++.h>
using namespace std;

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

const int INF=2000000000;
int R, C, mat[1005][1005], drum[1005][1005];
char x;
struct poz{
    int l, c;
};
queue<poz> Q;
poz start, finish;
int dl[4]={-1, 0, 1, 0};
int dc[4]={0, 1, 0, -1};

void LEE1(){
    while(Q.size()!=0){
        poz aux=Q.front();
        Q.pop();
        int l=aux.l;
        int c=aux.c;
        for(int k=0;k<4;k++)
            if(mat[l+dl[k]][c+dc[k]]==0 || (mat[l+dl[k]][c+dc[k]]!=INF && mat[l+dl[k]][c+dc[k]]>mat[l][c]+1)){
                 mat[l+dl[k]][c+dc[k]]=mat[l][c]+1;
                 Q.push({l+dl[k], c+dc[k]});
            }
    }
}
void clean(){
    for(int i=1;i<=R;i++)
        for(int j=1;j<=C;j++)
            if(drum[i][j]!=INF)
                drum[i][j]=0;
}

bool verif(int ct){
    clean();
    int l=start.l;
    int c=start.c;
    Q.push({l,c});
    drum[l][c]=1;
    while(Q.size()!=0){
        poz aux=Q.front();
        Q.pop();
        l=aux.l;
        c=aux.c;
        for(int k=0;k<4;k++){
            if(drum[l+dl[k]][c+dc[k]]==0 && mat[l+dl[k]][c+dc[k]]>=ct){
                drum[l+dl[k]][c+dc[k]]=drum[l][c]+1;
                Q.push({l+dl[k], c+dc[k]});
            }
        }
    }
    l=finish.l;
    c=finish.c;

    if(drum[l][c]!=0)
        return true;
    return false;
}

int cb(){
    int st=1, dr=2000, mij, p;
    while(st<=dr){
        mij=(st+dr)/2;
        if(verif(mij)){
            st=mij+1;
            if(mij>p)
                p=mij;
        }
        else dr=mij-1;
    }
    return p;
}

int main(){
    fin>>R>>C;
    for(int i=1;i<=R;++i)
        for(int j=1;j<=C;++j){
            fin>>x;
            if(x=='*'){
                mat[i][j]=INF;
                drum[i][j]=INF;
            }
            else if(x=='D')
                Q.push({i,j});
            else if(x=='I'){
                    start.l=i;
                    start.c=j;
                }
            else if(x=='O'){
                    finish.l=i;
                    finish.c=j;
                }
            else
                mat[i][j]=0;
        }
    for(int i=0;i<=R+1;++i){
        mat[i][0]=mat[i][R+1]=INF;
        drum[i][0]=drum[i][R+1]=INF;
    }
    for(int j=0;j<=C+1;++j){
        mat[0][j]=mat[C+1][j]=INF;
        drum[0][j]=drum[C+1][j]=INF;
    }
    LEE1();
    for(int i=1;i<=R;i++){
        for(int j=1;j<=C;j++){
            if(mat[i][j]==INF)
                fout<<"* ";
            else fout<<mat[i][j]<<" ";
        }
        fout<<"\n";
    }
    fout<<cb();
    return 0;
}