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

using namespace std;
ifstream f ("barbar.in");
ofstream g ("barbar.out");
int const NM = 1001 , di [] = {0 , 1 , 0 , -1} , dj [] = {1 , 0 , -1 , 0};
short d1 [NM][NM] , dp [NM][NM] , n , m , I1 , I2 , S1 , S2;
string s;
queue <pair <int , int> > Q;
inline bool valid (int x , int y){
    return x > 0 && y > 0 && x <= n && y <= m;
}
bitset <NM> mark [NM] , v [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]){
                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;
}
int main()
{
    int i , j;
    f >> n >> m;
    for(i = 1 ; i <= n ; ++ i){
        f >> s;
        string :: iterator it;
        int o = 1;
        for(it = s . begin () ; it != s . end () ; ++ it , ++ o){
            if (*it == 'I')
                I1 = i , I2 = o;
            if (*it == 'O')
                S1 = i , S2 = o;
            if (*it == '*')
                v [i][o] = 1;
            if (*it == 'D')
                Q . push (make_pair (i , o)) , mark [i][o] = 1;
        }
    }
    BF ();
    for(i = 1 ; i <= n ; ++ i){
        for (j = 1 ; j <= m ; ++ j)
            cout << dp [i][j] << ' ' ;
        cout << '\n';
    }
    int pas = (1 << 10) , found = 0;
    while (pas){
        if (pas + found <= n + m - 2 && check (pas + found))
            found += pas;
        pas /= 2;
    }
    if (! found)
        g << -1;
    else
        g << found;
    return 0;
}