#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <list>
using namespace std;

enum { dirs = 4, maxcoord = 1004, inf = 0x3f3f3f3f };
enum { wall = '*', empty = '.', dragon = 'D', begin = 'I', end = 'O' };

const int dir[dirs][2] =
{
	{  0,  1 },
	{  0, -1 },
	{  1,  0 },
	{ -1,  0 }
};

int rows, cols;
char grid[maxcoord][maxcoord]; //bordered

int todragon[maxcoord][maxcoord]; //distance to nearest dragon
int q[maxcoord * maxcoord], qs, qe; //queue item is row * maxcoord + col

int start;
list<int> *pos; //positions with min_dist i (dynamically alloc'd)
int best[maxcoord][maxcoord]; //from input, farthest from dragons

int ans;

void flood_todragon()
{
	int r, c, rr, cc, i, tmp;

	while(qe > qs)
	{
		//pop_front
		r = q[qs] / maxcoord;
		c = q[qs] % maxcoord;
		qs++;

		for(i = 0; i < dirs; i++)
		{
			rr = r + dir[i][0];
			cc = c + dir[i][1];

			if(grid[rr][cc] == wall)
				continue;

			tmp = todragon[r][c] + 1;
			if(tmp < todragon[rr][cc])
			{
				todragon[rr][cc] = tmp;
				q[qe++] = rr * maxcoord + cc;
			}
		}
	}
}

void calc_best()
/*
 * MBO: could stop when end reached
 */
{
	int r, c, rr, cc, i, tmp;

	while(true)
	{
		while(pos[start].empty() && start >= 0)
			start--;

		if(start < 0)
			break;

		r = *( pos[start].begin() ) / maxcoord;
		c = *( pos[start].begin() ) % maxcoord;
		pos[start].pop_front();

		if(best[r][c] < start) //stale item in list
			continue;

		for(i = 0; i < dirs; i++)
		{
			rr = r + dir[i][0];
			cc = c + dir[i][1];

			if(grid[rr][cc] == wall)
				continue;

			tmp = min(best[r][c], todragon[rr][cc]);
			if(tmp > best[rr][cc])
			{
				best[rr][cc] = tmp;
				pos[tmp].push_back(rr * maxcoord + cc);
			}
		}
	}
}

void go()
{
	int r, c, endr, endc;

	memset(todragon, 0x3f, sizeof(todragon));
	qs = qe = 0;
	for(r = 0; r < rows; r++) //MBO
		for(c = 0; c < cols; c++)
			if(grid[r][c] == dragon)
			{
				todragon[r][c] = 0;
				q[qe++] = r * maxcoord + c;
			}

	flood_todragon();

	//memset best 0
	endr = -1;
	for(r = 0; r < rows; r++) //MBO
		for(c = 0; c < cols; c++)
		{
			if(grid[r][c] == begin)
			{
				best[r][c] = todragon[r][c];

				if(best[r][c] != inf)
				{
					start = best[r][c];

					//there may not be anything bigger than this
					pos = new list<int>[start + 1];

					pos[start].push_back(r * maxcoord + c);
				}
				else
				{
					ans = -1; //BEGIN unreachable from dragons; dist is infinity
				}
			}
			else if(grid[r][c] == end)
			{
				endr = r;
				endc = c;
			}
		}

	if(ans != -1)
	{
		calc_best();

		ans = best[endr][endc];

		if(ans == 0) //END unreachable
			ans = -1;
	}
}

int main()
{
	int i;
	FILE *f = fopen("barbar.in", "r");
	if(!f) return 1;

	fscanf(f, "%d %d", &rows, &cols);
	
	//read
	for(i = 0; i < rows; i++)
		fscanf(f, " %s", grid[i + 1] + 1);

	//border
	for(i = 0; i < rows + 2; i++)
	{
		grid[i][0] = wall;
		grid[i][cols + 1] = wall;
	}
	for(i = 0; i < cols + 2; i++)
	{
		grid[0][i] = wall;
		grid[rows + 1][i] = wall;
	}
	rows += 2;
	cols += 2;

	fclose(f);
	f = fopen("barbar.out", "w");
	if(!f) return 1;

	go();

	fprintf(f, "%d\n", ans);
	fclose(f);
	return 0;
}