#include<bits/stdc++.h>

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

//NMAX-1 este dimensiunea maxima pe care o poate lua R si C
const int NMAX = 1001;
int n, m, harta[NMAX][NMAX];
bool Ex[NMAX][NMAX];
pair<int, int> pstart, pfinish;


char a[NMAX][NMAX];

queue<pair<int, int>> coada;
//pstart - coordonatele pozitiei de start ale lui Paftenie
// pfinish - iesirea din temnita
//R este numarul de linii ale matricei/temnitei
//C este numarul de coloane ale matrice/temnitei
// harta[][] este matricea asociata temnitei
int dx[] = {-1, 0, 1, 0}, // coordonata linie
        dy[] = {0, 1, 0, -1}; // coordonata coloana


void Read() {
    fin >> n >> m;

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
           //litera folosita la citirea si interpretarea caracterelor
            fin >> a[i][j];
// Notatii:
// . -o celula libera -> harta[i][j] = 0
// * -perete -> harta[i][j] = -1
// D -dragon ->harta[i][j]= -2
// I -punctul de plecare al lui Paftenie ->harta[i][j] = 0, pstart.first=i,pstart.second=j
// litera O -o iesire din temnita ->harta[i][j]= -3
            switch (a[i][j]) {
                case 'D':
                 coada.push(make_pair(i, j));
                    break;
                case 'I':
                    pstart.first = i, pstart.second = j;
                    break;
                case 'O':
                    pfinish.first = i, pfinish.second = j;
                    break;
                default:
                    break;
            }
        }

}

bool Ok(int i, int j) {
    return !(i < 1 || i > n  || j < 1 || j > m  || a[i][j] =='D' || a[i][j] == '*');
}

void BFS() {
    while (!coada.empty()) {
        int x = coada.front().first;
        int y = coada.front().second;
        coada.pop();

        for (int k = 0; k < 4; ++k) {
            int xnou = x + dx[k];
            int ynou = y + dy[k];

            if (Ok(xnou, ynou) && harta[xnou][ynou] == 0) {
                harta[xnou][ynou] = harta[x][y] + 1;
                coada.push(make_pair(xnou, ynou));
            }
        }
    }
}

bool BFSCheck(int x) {
    memset(Ex, 0, sizeof(Ex));
coada.push(pstart);
    while (!coada.empty()) {
        int x = coada.front().first;
        int y = coada.front().second;
        coada.pop();

        for (int k = 0; k < 4; ++k) {
            int xnou = x + dx[k];
            int ynou = y + dy[k];

            if (Ok(xnou, ynou) && harta[xnou][ynou] >= x && Ex[xnou][ynou] == false) {
                Ex[xnou][ynou] = true;
                coada.push(make_pair(xnou, ynou));

                if (xnou == pfinish.first && ynou == pfinish.second)
                    return true;
            }
        }
    }
    return false;
}

void Solve() {
    bool valid = true;
    for (int i = harta[pstart.first][pstart.second] && valid; i >= 1; --i)
        if (BFSCheck(i) == true) {
            fout << i;
            valid=false;
           // return;
        }
        //fout << -1;
}


int main() {
    Read();

    BFS();

    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j)
            cout<<harta[i][j]<<' ';
        cout<<endl;}
   Solve();

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

/*
IDEI:
{1}
1.Algoritm de fill initial in care se memoreaza intr-o matrice
toate distantele de la fiecare celula libera la un dragon apoi o
functie ce returneaza pozitia dintre vecini cea mai avantajoasa
{1}
AVANTAJE:
Rapiditate in accesarea unor posibile pozitii favorabile
{1}
DEZAVANTAJE:
Consum mare de memorie **Nota memoria e echivalenta cu un array de 16 mil de elemente
{1}
*/