#include <iostream>
#include <fstream>
#include <queue>

#define l first
#define c second

using namespace std;

const int NMAX = 1002;

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

int N, M;
int sl, sc, fl, fc;

int dl[] = { 1, -1, 0, 0 };
int dc[] = { 0, 0, 1, -1 };

queue < pair <int,int> > Q;
int Mat[NMAX][NMAX];
bool V[NMAX][NMAX];

void Read()
{
    char c;
    fin >> N >> M;

    for( int i = 1; i <= N; ++i )Mat[i][0] = Mat[i][M+1] = -1;
    for( int i = 1; i <= M; ++i )Mat[0][i] = Mat[N+1][i] = -1;

    for( int i = 1; i <= N; i -=- 1 )
        for( int j = 1; j <= M; j -=- 1)
    {
        fin >> c;
        if( c == 'I' )
        {
            sl = i;
            sc = j;
        }
        if( c == 'O')
        {
            fl = i;
            fc = j;
        }
        if( c == 'D' )
        {
            Q.push( make_pair(i,j) );
            //Mat[i][j] = -1;
        }
        if( c == '*' )
        {
            Mat[i][j] = -1;
        }
    }

    /*for( int i = 0; i <= N+1; ++i )
    {
        for( int j = 0; j <= M+1; ++j )
        {
            if( Mat[i][j] == -1 )
                fout << '#' << ' ';
            else fout << Mat[i][j] << ' ';
        }
        fout << '\n';
    }*/
}

void Solve()
{
    int x, y, xv, yv;
    while( Q.size() )
    {
        x = Q.front().l;
        y = Q.front().c;
        Q.pop();

        for( int k = 0; k < 4; ++k )
        {
            xv = x + dl[k];
            yv = y + dc[k];

            if( Mat[xv][yv] == 0 )
            {
                Mat[xv][yv] = Mat[x][y] + 1;
                Q.push( make_pair( xv, yv ) );
            }
        }
    }

    priority_queue < pair<int, int> > PQ;
    PQ.push( make_pair (fl, fc) );
    V[fl][fc] = 1;

    while( PQ.size() )
    {
        x = PQ.top().l;
        y = PQ.top().c;
        PQ.pop();

        for( int k = 0; k < 4; ++k )
        {
            xv = x + dl[k];
            yv = y + dc[k];

            if( Mat[xv][yv] != -1 && V[xv][yv] == 0)
            {
                V[xv][yv] = 1;
                Mat[xv][yv] = min( Mat[xv][yv], Mat[x][y] );
            }
        }
    }
    for( int i = 0; i <= N+1; ++i )
    {
        for( int j = 0; j <= M+1; ++j )
        {
            if( Mat[i][j] == -1 )
                fout << '#' << ' ';
            else fout << Mat[i][j] << ' ';
        }
        fout << '\n';
    }
    fout << Mat[sl][sc];
}
int main()
{
    Read();
    Solve();
    return 0;
}