#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

//constanta ce ajuta la memorarea a celor doua coordonate intregi ca un singur numar in coada de parcurgere
#define D 1024

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

//vectori de deplasare pentru cele 4 direrctii
int di[4] = {-1, 1, 0, 0};
int dj[4] = {0, 0, -1, 1};


//distanta maxima posibila, care este data de distanta minima dintre un dragon si I
//sau dintre un dragon si 'O'
int dmax;

int R, C;
//coordonatele sursei si destinatiei
int Ii, Ji, If, Jf;

//matricea care retine distantele de la un spatiu liber pana la cel mai apropia dragon
vector<vector<int>> d;

vector<vector<char>> m;
//matricea de lucru, cea pe care o putem modifica
vector<vector<char>> a;

//matricea in care se va marca ce celule au fost vizitate(folosita la parcurgerea in latime)
vector<vector<bool>> vizitat;

//functie care testeaza daca ne aflam in interiorul matricei
bool inside(int i, int j)
{
    if(i >= 0 && i < R && j >=0 && j < C)
        return true;

    return false;
}

//subprogram pentru determinarea disantelor(umple matricea d)
int distante()
{
    //distanta maxima posibila, care este data de distanta minima dintre un dragon si I
    //sau dintre un dragon si 'O'
    int dmax;

    queue<int> q;
    vizitat.resize(R, vector<bool>(C));

    //parcurgem matricea pentru a gasi dragonii;
    //odata gasit un dragon, acesta este pus in coada
    for(int i = 0; i < R; ++i)
        for(int j = 0; j < C; ++j)
            if(m[i][j] == 'D')
            {
                q.push(i*D+j);
                vizitat[i][j] = true;
            }

    while(!q.empty())
    {
        //extragem urmatoarea celula din coada
        int x = q.front();
        q.pop();

        //aflam coordonatele celulei extrase din coada
        int i = x/D;
        int j = x%D;

        //incercam deplasare in fiecare din cele 4 directii posibile
        for(int k=0; k<4; ++k)
        {
            int ni = i + di[k]; //noul i
            int nj = j + dj[k]; //noul j

            //verificam daca deplasandu-ne astfel ramanem in continuare in matrice,
            //celula este libera si celula nu a mai fost vizitata
            if(inside(ni,nj) && !vizitat[ni][nj] && m[ni][nj] == '.')
            {
                vizitat[ni][nj] = true;
                q.push(ni*D+nj);
                d[ni][nj] = d[i][j] + 1;

                if(m[ni][nj] == 'I' || m[ni][nj]=='O')
                    dmax = d[ni][nj];
            }
        }
    }
    return dmax;
}

//subpogram care determina distanta maxima posibila, care este data de distanta minima dintre un dragon si I
//sau dintre un dragon si 'O'
//int dmax()
//{
//    //matrice care retine distanta de la fiecare dragon pana la fiecare celula din traseul parcurs
//    vector<vector<int>> d(R, vector<int>(C));
//
//
//    //pregatim matricea de vizitat pentru urmatoarea parcurgere
//    vizitat.clear();
//    vizitat.resize(R, vector<bool>(C));
//
//    //coada folosita la parcurgerea in latime
//    queue<int> q;
//
//    q.push(Ii*D+Ji);
//    q.push(If*D+Jf);
//    vizitat[Ii][Ji] = true;
//    vizitat[If][Jf] = true;
//
//    while(!q.empty())
//    {
//        //extragem urmatoarea celula din coada
//        int x = q.front();
//        q.pop();
//
//        //aflam coordonatele celulei extrase din coada
//        int i = x/D;
//        int j = x%D;
//
//        //incercam deplasare in fiecare din cele 4 directii posibile
//        for(int k=0; k<4; ++k)
//        {
//            int ni = i + di[k]; //noul i
//            int nj = j + dj[k]; //noul j
//
//            //verificam daca deplasandu-ne astfel ramanem in continuare in matrice,
//            //celula este libera, celula nu a mai fost vizitata si distanta este mai mica decat dist
//            if(inside(ni,nj) && !vizitat[ni][nj] && ( a[ni][nj] == 'D' || a[ni][nj] == '.') )
//            {
//                vizitat[ni][nj] = true;
//                q.push(ni*D+nj);
//                d[ni][nj] = d[i][j] + 1;
//
//                if(a[ni][nj] == 'D')
//                    return d[ni][nj];
//            }
//        }
//    }
//    return 0;
//}


//subprogram ce pune in matricea de lucru a pereti in jurul fiecarui dragon pe o raza egala cu distanta propusa
//data subprogramului "parcurgere"
void umplere(int dist)
{

    for(int i=0; i<R; ++i)
        for(int j=0; j<C; ++j)
            if(a[i][j] == '.' && d[i][j] <= dist)
                a[i][j] = '*';

}

//functia de parcurgere in latime, care primeste o distanta minima fata de dragoni propusa
//si returneaza distanta primita daca parcurgerea este posibila sau -1 in caz contrar
int parcurgere(int dist)
{
    //copiem matricea m in matricea de lucru a
    a.resize(R, vector<char>(C));
    for(int i = 0; i < R; ++i)
        for(int j = 0; j < C; ++j)
            a[i][j] = m[i][j];

    if(dist > 1)
        umplere(dist-1);


    //pregatim matricea de vizitat pentru urmatoarea parcurgere
    vizitat.clear();
    vizitat.resize(R, vector<bool>(C));

    //coada folosita la parcurgerea in latime
    queue<int> q;

    //vizitam celula sursa
    q.push(Ii*D+Ji);
    vizitat[Ii][Ji] = true;

    while(!q.empty())
    {
        //extragem urmatoarea celula din coada
        int x = q.front();
        q.pop();

        //aflam coordonatele celulei extrase din coada
        int i = x/D;
        int j = x%D;

        //incercam deplasare in fiecare din cele 4 directii posibile
        for(int k=0; k<4; ++k)
        {
            int ni = i + di[k]; //noul i
            int nj = j + dj[k]; //noul j

            //verificam daca deplasandu-ne astfel ramanem in continuare in matrice,
            //celula este libera si celula nu a mai fost vizitata
            if(inside(ni,nj) && !vizitat[ni][nj] && (a[ni][nj] == '.' || a[ni][nj] =='O' || a[ni][nj] =='D'))
            {
                //daca s-a ajuns in destinatie
                if(ni == If && nj == Jf)
                    return dist;

                vizitat[ni][nj] = true;
                q.push(ni*D+nj);
            }
        }
    }

    //nu s-a putut ajunge in destinatie
    return -1;
}

//functia care cauta binar distanta optima ce poate fi propusa functiei parcurgere,
//astfel incat sa se poata ajunge in destinatie
int solve()
{
    //testam daca este posibil sa ajungem din sursa in destinatie
    int rez = parcurgere(0);
    if(rez == -1)
        return rez;

    //valorile intre care cautam binar
    int st = 0;

    //int dr = dmax();
    int dr = dmax;

    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        int r = parcurgere(mij);

        //daca parcurgerea nu este posibila, inseamna ca distanta propusa este prea mare
        //si trebuie micsorata
        if(r == -1)
            dr = mij - 1;
        else //in caz contrat inseamna ca parcurgerea este posibila si incrcam sa marim distanta propusa
        {
            st = mij + 1;
            //daca am gasit o distanta mai buna decat pana in acest punct
            if(rez < r)
                rez = r;
        }
    }

    return rez;
}


int main()
{
    fin >> R >> C;

    //dimensionam matricea
    m.resize(R, vector<char>(C));

    //dimensionam matricea care retine distantele de la un spatiu liber pana la cel mai apropia dragon
    d.resize(R, vector<int>(C));

    //citim datel din matrice
    for(int i=0; i<R; ++i)
        for(int j=0; j<C; ++j)
        {
            fin >> m[i][j];
            //determinam coordonatele sursei si ale destinatiei
            if(m[i][j] == 'I')
            {
                Ii = i;
                Ji = j;
                d[Ii][Ji] = -1;
            }
            if(m[i][j] == 'O')
            {
                If = i;
                Jf = j;
                d[If][Jf] = -1;
            }
        }


    dmax = distante();

    fout << solve();
}