//#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};
//
//
//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)
//void distante()
//{
//    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;
//            }
//        }
//    }
//}
//
////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 innlatime, 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();
//
//    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;
//            }
//        }
//
//    distante();
//
//    fout << solve();
//}