/*
#include <iostream>
#include <fstream>
#include <queue>

#define pii pair <int, int>
#define LIBER 0
#define PERETE 1
#define DRAGON 2

using namespace std;

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

const int N = 1000;
int original[N + 1][N + 1], harta[N + 1][N + 1], n, m;
bool reach[N + 1][N + 1];

/// ordine N, E, S, V:
int diri[] = {-1, 0, 1, 0};
int dirj[] = {0, 1, 0, -1};

void clear_harta(){
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= N; j++)
            reach[i][j] = harta[i][j] = 0;
}

bool in_bounds(int i, int j){
    return (1 <= i && i <= n && 1 <= j && j <= m);
}

void my_fill(pii nod){
    reach[nod.first][nod.second] = true;
    for(int dir = 0; dir < 4; dir++){
        if(!reach[nod.first + diri[dir]][nod.second + dirj[dir]] && harta[nod.first + diri[dir]][nod.second + dirj[dir]] == LIBER && in_bounds(nod.first + diri[dir], nod.second + dirj[dir]))
            my_fill({nod.first + diri[dir] ,nod.second + dirj[dir]});
    }
}

int main(){
    pii intrare, iesire;
    fin >> n >> m;
    char ch;
    fin.get(ch); /// '\n'
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            fin.get(ch);
            if(ch == 'I') intrare = {i, j};
            if(ch == 'O') iesire = {i, j};
            if(ch == 'D') original[i][j] = DRAGON;
            if(ch == '*') original[i][j] = PERETE;
        }
        fin.get(ch); /// '\n'
    }
    int st = 0, dr = N, ans = -1;
    while(st <= dr){
        clear_harta();
        int dist = (st + dr) / 2;
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                harta[i][j] = original[i][j];
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(original[i][j] == DRAGON){
                    for(int dir = 0; dir < 4; dir++){
                        int x = i, y = j;
                        for(int k = 0; k < dist; k++){
                            x += diri[dir];
                            y += dirj[dir];
                            if(in_bounds(x, y) && original[x][y] == LIBER) harta[x][y] = PERETE;
                            else break;
                        }
                    }
                }
            }
        }
        my_fill(intrare);

        if(reach[iesire.first][iesire.second]) ans = dist, st = dist + 1;
        else dr = dist - 1;
    }
    if(ans != -1) ans++;
    fout << ans;
    return 0;
}
**/

// eu iau 50p si n am chef de debug, scz

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const string fn = "barbar";

ifstream fin(fn + ".in");
ofstream fout(fn + ".out");

int n, m;
int xi, yi, xo, yo;

int d[1005][1005];
char a[1005][1005];
bitset<1003> v[1003];

inline bool in(int &i, int &j)
{
    return 1 <= i && i <= n && 1 <= j && j <= m;
}

const int dx[] = { -1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

queue<pair<int, int> > q;

void f()
{
    int i, j, x, y;
    while (!q.empty())
    {
        i = q.front().first;
        j = q.front().second;
        q.pop();
        for (int k = 0; k < 4; ++k)
        {
            x = i + dx[k];
            y = j + dy[k];
            if (in(x, y) && d[x][y] > d[i][j] + 1 && a[x][y] != '*')
            {
                d[x][y] = d[i][j] + 1;
                q.push({x, y});
            }
        }
    }
}




void fl(int i, int j, int val)
{
    int x, y;
    stack<pair<int , int > > s;
    s.push({i, j});
    while (!s.empty())
    {
        i = s.top().first;
        j = s.top().second;
        s.pop();
        for (int k = 0; k < 4; ++k)
        {
            x = i + dx[k];
            y = j + dy[k];
            if (in(x, y) && !v[x][y] && d[x][y] >= val && a[x][y] != '*')
            {
                v[x][y] = 1;
                if (x == xo && y == yo)
                    return;
                s.push({x, y});
            }
        }
    }
}

int main()
{

    fin >> n >> m;
    for (int i = 1; i <= n; ++i)
        fin >> (a[i] + 1);

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            d[i][j] = 2000000;

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (a[i][j] == 'I') xi = i, yi = j;
            else if (a[i][j] == 'O') xo = i, yo = j;
            else if (a[i][j] == 'D') q.push({i, j}), d[i][j] = 0;
    f();

    int st, dr, mid, ans;
    st = 1; dr = d[xi][yi];
    ans = -1;
    while (st <= dr)
    {
        mid = (st + dr) >> 1;
        for (int i = 1; i <= n; ++i)
            v[i].reset();
        fl(xi, yi, mid);
        if (v[xo][yo] == 1)
        {
            ans = mid;
            st = mid + 1;
        }
        else dr = mid - 1;
    }
    fout << ans << '\n';

    fin.close();
    fout.close();
    return 0;
}