#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

using namespace std;

#define file_input "barbar.in"
#define file_output "barbar.out"

#define MAX_DIM 1000
#define MAX_DIM_DIM (MAX_DIM * MAX_DIM)

const int dif_l[] = {0,-1,0,1};
const int dif_c[] = {-1,0,1,0};

int R, C;
char M[MAX_DIM][MAX_DIM];
short D[MAX_DIM][MAX_DIM];
int start, end;
char Viz[MAX_DIM_DIM];

// vector <int> dragons;

inline int crd ( int i , int j ) {

	return C*i + j;
}

inline void b_crd ( int pos , int& x, int& y) {

	x = pos/C;
	y = pos%C;
}

void calc_D ( int s_pos ) {
	
	Viz [s_pos] = 1;
	list<int> parc;
	int x, y;

	b_crd(s_pos,x,y);
	D[x][y] = 0;
	
	parc.push_back(s_pos);
	while (!parc.empty()) {

		int pos = parc.front();
		parc.pop_front();
		
		b_crd(pos,x,y);
		for(int k=0;k<4;++k) {

			int l = x+dif_l[k];
			int c = y+dif_c[k];

			if ( l < 0 || c < 0 || l >= R || c >= C ) continue;
			
			switch ( M[l][c] ) {

				case 0: if ( D[l][c] == 0 || D[l][c] > ( D[x][y] + 1) ) {
						D[l][c] = D[x][y] + 1;
						parc.push_back(crd(l,c));
					}
					break;	
				case 1: break;
				case 2: D[l][c] = 0; Viz[crd(l,c)]=1; parc.push_back(crd(l,c)); break;
				default : printf("Error 1: M[%d][%d] = %d \n", l , c , M[l][c]); exit(-1);
			}
		}
	}
}

int can_do ( int d ) {

	int x, y;
	b_crd(start,x,y);
	if ( D[x][y] < d ) return 0;
	list<int> parc;
	memset(Viz,0,MAX_DIM_DIM);
	parc.push_back(start);
	Viz[start] = 1;
	
	while(!parc.empty()) {

		int pos = parc.front();	
		parc.pop_front();
		
		b_crd(pos,x,y);
		//cout << x << " " << y << endl;
		for(int k=0;k<4;++k) {

			int l = x+dif_l[k];
			int c = y+dif_c[k];

			int new_pos = crd(l,c);
			
			if ( Viz[new_pos] || M[l][c] >0 || D[l][c] < d  || ( l < 0 || c < 0 || l >= R || c >= C )  ) continue;
			
			if ( new_pos == end ) return 1;
			
			Viz[ new_pos ] = 1;
			parc.push_back ( new_pos );
		}
	}

	return 0;
}

int main ( void ) {

	

	FILE* fin = fopen(file_input,"r");
	FILE* fout = fopen(file_output,"w");

	return 0;
	
	fscanf(fin,"%d %d", &R, &C);
	
	int i, j;
	char c;
	for(i=0;i<R;++i) {
		fgetc(fin);
		for(j=0;j<C;++j) {
	
			fscanf(fin,"%c", &c);
			switch (c) {

				case '.' : break;
				case '*' : M[i][j] = 1; break;
				case 'I' : start = crd(i,j); break;
				case 'O' : end = crd(i,j); break;
				case 'D' : M[i][j] = 2; /*dragons.push_back(crd(i,j));*/ break;
				default : printf("Wrong input!\n"); return -1;
			}
		}
	}

	fclose(fin);
	
	/*
	for(i=0;i<dragons.size();++i) {

		int pos = dragons[i];
		if ( !Viz [pos] ) calc_D(pos);
	}
	*/

	for(i=0;i<R;++i)
		for(j=0;j<C;++j) 
			if ( M[i][j] == 2 && !Viz[ crd(i,j) ] ) calc_D(crd(i,j));

	/*
	for(i=0;i<R;++i, cout<<endl)
		for(j=0;j<C;++j, cout << " ")
			cout << D[i][j];
	*/

	/* Binary Search : */

	// cout << can_do(2)<<endl;
	return 0;
	int s = 1, e=R+C;
	while (e > s+1) {
		// cout << s << " " << e << endl;
		int m = (e-s) / 2;
		if ( can_do (m) ) s=m;
		else e = m-1;
	}

	if ( s==e ) if ( s != 1 || ( s == 1 && can_do(1) )) fprintf(fout,"%d\n", s);
                    else fprintf(fout,"-1\n");
	if ( e-s == 1 ) if ( can_do (e) ) fprintf(fout,"%d\n",e);
			else if ( s != 1 || ( s == 1 && can_do(1) )) fprintf(fout,"%d\n", s);
				else fprintf(fout,"-1\n");

	fclose(fout); 		
	return 0;
}