#include <fstream>
#include <queue>
#include <vector>
#include <utility>
#include <cstring>
#define FOR(i,a,b) for(int i = a; i<=b; i++)
#define NMAX 1005
using namespace std;
ifstream fin("barbar.in");
ofstream fout("barbar.out");
char mat[NMAX][NMAX];
int f[NMAX][NMAX];
bool fp[NMAX][NMAX];
vector<pair<int,int> > drag;
int xfi,yfi,xst,yst;
int dl[5] = {-1,0,1,0};
int dc[5] = {0,1,0,-1};
int sol;
int N,M;
void Citire();
void InitializationFill();
int CautareBinara();
bool Verificare(int x);
int main()
{
Citire();
InitializationFill();
/* FOR(i,1,N)
{
FOR(j,1,M)
fout<<f[i][j]<<" ";
fout<<'\n';
}*/
fout<<CautareBinara()<<'\n';
return 0;
}
bool Verificare(int dist)
{
FOR(i,1,N)
memset(fp[i],0,sizeof(fp[i]));
queue<pair<int,int> > Q;
Q.push(make_pair(xst,yst));
fp[xst][yst] == 1;
bool found = false;
while(!Q.empty())
{
int x = Q.front().first;
int y = Q.front().second;
Q.pop();
FOR(j,0,3)
{
int nx = x + dl[j];
int ny = y + dc[j];
if(fp[nx][ny] == 0 && f[nx][ny]!= -1 && f[nx][ny] - 1 >= dist)
{
fp[nx][ny] = 1;
if(nx == xfi && ny == yfi)
{
return true;
}
Q.push(make_pair(nx,ny));
}
}
}
return fp[xfi][yfi];
}
int CautareBinara()
{
int st = 0, fi = 2*NMAX,mij;
bool val;
sol = -NMAX;
while(fi-st > 1)
{
mij = (fi+st)/2;
val = Verificare(mij);
if(val == true)
{
sol = max(sol,mij);
st = mij;
}
else
{
fi = mij;
}
}
if(fi == 2*NMAX || sol == -NMAX)
return -1;
return sol;
}
void Citire()
{
fin>>N>>M;
FOR(i,1,N)
FOR(j,1,M)
{
fin>>mat[i][j];
if(mat[i][j] == '*')
f[i][j] = -1;
else if(mat[i][j] == 'D')
{
f[i][j] = -2;
drag.push_back(make_pair(i,j));
}
else if(mat[i][j] == 'O')
{
xfi = i;
yfi = j;
}
else if(mat[i][j] == 'I')
{
xst = i;
yst = j;
}
}
}
void InitializationFill()
{
FOR(i,0,M+1)
f[0][i] = f[N+1][i] = -1;
FOR(i,0,N+1)
f[i][0] = f[i][M+1] = -1;
FOR(i,0,(drag.size()-1))
{
queue<pair<int, int> > Q;
Q.push(drag[i]);
f[drag[i].first][drag[i].second] = 1;
while(!Q.empty())
{
int x = Q.front().first;
int y = Q.front().second;
Q.pop();
FOR(j,0,3)
{
int nx = x + dl[j];
int ny = y + dc[j];
if(f[nx][ny]!= -1 && (f[nx][ny] == 0 || f[nx][ny] > f[x][y] + 1))
{
f[nx][ny] = f[x][y]+1;
Q.push(make_pair(nx,ny));
}
}
}
/* FOR(k,0,N+1)
{
FOR(j,0,M+1)
fout<<f[k][j]<<" ";
fout<<'\n';
}
fout<<'\n'<<'\n';
*/}
}