// Barbar.cpp : Defines the entry point for the console application.
//

#include <stdio.h>
//#include <conio.h>
#include <math.h>
#pragma warning(disable : 4996)

int r, c, sx, sy, ex, ey;
char map[1000][1000];
struct
{
	long dd;
	long lee;
} lee[1000][1000] = {{0, 0}};
struct{
	int x, y;
} dragoon[1000*1000] = {(0,0)};
long numdragoons = 0;

void FillLee()
{
	for(int y=0;y<r;y++)
	{
		for(int x=0;x<c;x++)
		{
			long mindist = 999999999;
			for(long i=0;i<numdragoons;i++)
			{
				long d = abs(x-dragoon[i].x) + abs(y-dragoon[i].y);
				if (mindist > d) mindist = d;
			}
			lee[y][x].dd = mindist;
		}
	}
};

bool GoLee(int x, int y, long mindist)
{
	long dx, dy;
	bool rv = lee[ey][ex].lee != 0;

	lee[y][x].lee = mindist;
	char tc = map[y][x];
	map[y][x] = '*';

	dx = x-1; dy = y;
	if (dx >= 0)
		if (lee[dy][dx].dd >= mindist && map[dy][dx] != '*')
			rv = GoLee(dx, dy, mindist);
	if (rv) return true;

	dx = x+1; dy = y;
	if (dx < c)
		if (lee[dy][dx].dd >= mindist && map[dy][dx] != '*')
			rv = GoLee(dx, dy, mindist);
	if (rv) return true;

	dx = x; dy = y+1;
	if (dy < r)
		if (lee[dy][dx].dd >= mindist && map[dy][dx] != '*')
			rv = GoLee(dx, dy, mindist);
	if (rv) return true;

	dx = x; dy = y-1;
	if (dy >= 0)
		if (lee[dy][dx].dd >= mindist && map[dy][dx] != '*')
			rv = GoLee(dx, dy, mindist);
	if (rv) return true;

	map[y][x] = tc;
	return rv;
}

int main(int argc, char* argv[])
{
	int i, j;
	FILE *f = fopen("barbar.in", "r");
	fscanf(f, "%d %d\n", &r, &c);
	for(i=0;i<r;i++)
	{
		fgets(&map[i][0], 1000, f);
		for(j=0;j<c;j++)
		{
			switch(map[i][j])
			{
			case 'I': sx = j; sy = i; break;
			case 'O': ex = j; ey = i; break;
			case 'D': dragoon[numdragoons].x = j; dragoon[numdragoons].y = i; numdragoons++; break;
			}
		}
	}
	fclose(f);

	FillLee();

	long mindist;
	bool rv = false;
	for(mindist = lee[sy][sx].dd; mindist >= 1 && !rv; mindist--)
		rv = GoLee(sx, sy, mindist);

	if (!rv) mindist = -1;

	f = fopen("barbar.out","w");
	fprintf(f, "%ld", lee[ey][ex].lee);
	fclose(f);

	return 0;
}