#include <fstream>
#include <queue>
#include <iostream>
//#include <bitset>
#include <cstring>

using namespace std;
ofstream g ("barbar.out");
int const NM = 1001 , di [] = {0 , 1 , 0 , -1} , dj [] = {1 , 0 , -1 , 0};
int dp [NM][NM] , n , m , I1 , I2 , S1 , S2;
char s [NM];
queue <pair <int , int> > Q;
inline bool valid (int x , int y){
    return x > 0 && y > 0 && x <= n && y <= m;
}
bool mark [NM][NM] , v [NM][NM];
inline void BF (){
    while (! Q . empty ()){
        int x1 = Q . front () . first;
        int y1 = Q . front () . second;
        for(int o = 0 ; o < 4 ; ++ o){
            int x = x1 + di [o];
            int y = y1 + dj [o];
            if (valid (x , y) && ! mark [x][y] && ! v [x][y]){
                dp [x][y] = 1 + dp [x1][y1];
                mark [x][y] = 1;
                Q . push (make_pair (x , y));
            }
        }
        Q . pop ();
    }
}
inline bool check (int dist){
    if (dp [I1][I2] < dist)
        return false;
    for(int i = 1 ; i <= n ; ++ i)
        for(int j = 1 ; j <= m ; ++ j)
            mark [i][j] = 0;
    while (! Q . empty ())
        Q . pop ();
    Q . push (make_pair (I1 , I2));
    mark [I1][I2] = 1;
    while (! Q . empty ()){
        int x1 = Q . front () . first;
        int x2 = Q . front () . second;
        for(int i = 0 ; i < 4 ; ++ i){
            int x = x1 + di [i];
            int y = x2 + dj [i];
            if (x == S1 && y == S2 && dp [x][y] >= dist)
                return true;
            if (valid (x , y) && dp [x][y] >= dist && ! mark [x][y] && ! v [x][y]){
                Q . push (make_pair (x , y));
                mark [x][y] = 1;
            }
        }
        Q . pop ();
    }
    return false;
}
inline bool validc (char x){
    return x == '.' || x == 'D' || x == 'O' || x == '*';
}
int main()
{
    int i , j;
    freopen ("barbar.in" , "r" , stdin);
    scanf ("%d %d" , &n , &m);
    for(i = 1 ; i <= n ; ++ i){
        scanf ("%s" , s);
        int o2 = 1;
        for(int o = 0 ; o < m ; ++ o , ++ o2){
            if (s [o] == 'I')
                I1 = i , I2 = o2;
            if (s [o] == 'O')
                S1 = i , S2 = o2;
            if (s [o] == '*')
                v [i][o2] = 1;
            if (s [o]  == 'D')
                Q . push (make_pair (i , o2)) , mark [i][o2] = 1;
        }
    }
    BF ();
    for(i = 1 ; i <= n ; ++ i){
        for (j = 1 ; j <= m ; ++ j)
            cout << dp [i][j] << ' ' ;
        cout << '\n';
    }
    int from = 1 , to = 2048 , found;
    while (from <= to){
        int mid = (from + to) / 2;
        if (check (mid)){
            found = mid;
            from = mid + 1;
        }
        else
            to = mid - 1;
    }
  /*  while (pas){
        if (check (pas + found))
            found += pas;
        pas /= 2;
    } */
    if (! found)
        -- found;
    g << found;
    return 0;
}