#include <fstream>
#include <queue>
using namespace std;

ifstream cin("barabar.in");
ofstream cout("barbar.out");

int n,m,lin,col,clin,ccol,lfin,cfin,linc,cinc,dlin[4]={-1,0,1,0},dcol[4]={0,1,0,-1},mat[1000][1000],dis[1000][1000],mat2[1000][1000],dis2[1000][1000];

queue<pair<int,int>>q;

int cond(int x){
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            dis2[i][j]=-1;
            mat2[i][j]=0;
        }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(dis[i][j]<x && dis[i][j]!=-1){
                mat2[i][j]=1;
                dis2[i][j]=-2;
            }
        }
    }
    if(dis[linc][cinc]<x)
        return 0;
    dis2[linc][cinc]=0;
    q.push({linc,cinc});
    while(q.empty()==0){
        lin=q.front().first;
        col=q.front().second;
        q.pop();
        for(int i=0;i<4;i++){
            clin=lin+dlin[i];
            ccol=col+dcol[i];
            if(clin>=0 && clin<n && ccol>=0 && ccol<m && mat2[clin][ccol]==0 && dis2[clin][ccol]==-1){
                dis2[clin][ccol]=dis2[lin][col]+1;
                q.push({clin,ccol});
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)
            cout<<dis2[i][j]<<" ";
        cout<<"\n";
    }
    if(dis2[lfin][cfin]!=-1)
        return 1;
    return 0;
}

int main()
{
    int st,dr,mid;
    char ch;
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            cin>>ch;
            if(ch=='.')
                dis[i][j]=-1;
            else if(ch=='*'){
                dis[i][j]=-2;
                mat[i][j]=1;
            }
            else if(ch=='D')
                q.push({i,j});
            else if(ch=='I'){
                linc=i;
                cinc=j;
            }
            else{
                lfin=i;
                cfin=j;
            }
        }
    while(q.empty()==0){
        lin=q.front().first;
        col=q.front().second;
        q.pop();
        for(int i=0;i<4;i++){
            clin=lin+dlin[i];
            ccol=col+dcol[i];
            if(clin>=0 && clin<n && ccol>=0 && ccol<n && mat[clin][ccol]==0 && dis[clin][ccol]==-1){
                dis[clin][ccol]=dis[lin][col]+1;
                q.push({clin,ccol});
            }
        }
    }
    dr=n+m;
    st=0;
    while(st<=dr){
        mid=(st+dr)/2;
        if(cond(mid)==1)
            st=mid+1;
        else
            dr=mid-1;
        cout<<"\n";
    }
    cout<<dr;
    return 0;
}