#include<bits/stdc++.h>
using namespace std;
ifstream fin("barbar.in");
ofstream fout("barbar.out");
int dist[1001][1001], n, m; //dist[i][j]=distanta minima de la pctul de start pana la pozitia [i][j]
const int di[]={-1, 0, 1, 0}, dj[]={0, 1, 0, -1};
char v[1001][1001], v2[1001][1001];
void refresh()
{
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            v[i][j]=v2[i][j];
}
bool check(int i, int j)
{
    if(i>=1 && i<=n && j>=1 && j<=m)
        return 1;
    return 0;
}
void Fill(int i, int j, int val)
{
    if(check(i, j) && (v[i][j]=='I' || v[i][j]=='.' || v[i][j]=='O') && dist[i][j]>=val)
    {
        v[i][j]=0;
        for(int k=0; k<4; k++)
            Fill(i+di[k], j+dj[k], val);
    }
}
void lee(queue<pair<int, int>>q)
{
    while(!q.empty())
    {
        int i=q.front().first, j=q.front().second;
        q.pop();
        for(int k=0; k<4; k++)
        {
            if(check(i+di[k], j+dj[k]) && v[i+di[k]][j+dj[k]]!='*')
            {
                if(dist[i][j]+1<dist[i+di[k]][j+dj[k]]){
                    dist[i+di[k]][j+dj[k]]=dist[i][j]+1;
                    q.push({i+di[k], j+dj[k]});
                }
            }
        }
    }
}
int main()
{
    fin >> n >> m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            fin >> v[i][j];
    queue<pair<int,int>>q;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            dist[i][j]=20;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if(v[i][j]=='D'){
                dist[i][j]=0;
                q.push({i, j});
            }
    lee(q);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++)
            cout << dist[i][j] << " ";
        cout << "\n";
    }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            v2[i][j]=v[i][j];
    int mn=2e9, mx=0, starti, startj, endi, endj;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++){
            if(dist[i][j]==2e9 || dist[i][j]==0)
                continue;
            mn=min(mn, dist[i][j]);
            mx=max(mx, dist[i][j]);
            if(v[i][j]=='O')
            {
                endi=i;
                endj=j;
            }
            else if(v[i][j]=='I')
            {
                starti=i;
                startj=j;
            }
        }
    int st=mn, dr=mx, mij, poz=-1;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        Fill(starti, startj, mij);
        if(v[endi][endj]==0)
        {
            st=mij+1;
            poz=mij;
        }
        else
            dr=mij-1;
        refresh();
    }
    fout << poz;
    return 0;
}