#include <stdio.h>
const int dx[]={-1, 0, 1,  0};
const int dy[]={ 0, 1, 0, -1};
int r, c, xi, yi, xf, yf;
long qx[1000010], qy[1000010], p=0, u=-1, h[1010][1010];
bool fol[1010][1010];

void bfs();
long bsearch();
int bfsm(long m);

int main()
{
	char aux;
	int i, j;
	freopen("barbar.in", "r", stdin);
	freopen("barbar.out", "w", stdout);
	scanf("%d%d", &r, &c);
	scanf("%c", &aux);
	for (i=1; i<=r; i++)
	{
		h[i][0]=-1;
		h[i][c+1]=-1;
		for (j=1; j<=c; j++)
		{
			scanf("%c", &aux);
			if (aux=='D')
			{
				h[i][j]=0;
				u++;
				qx[u]=i;
				qy[u]=j;
			}//if
			if (aux=='.')
				h[i][j]=-2;
			if (aux=='*')
				h[i][j]=-1;
			if (aux=='I')
			{
				h[i][j]=-2;
				xi=i;
				yi=i;
			}//if
			if (aux=='O')
			{
				h[i][j]=-2;
				xf=i;
				yf=i;
			}//if			
		}//for j
		scanf("%c", &aux);
	}//for i
	for (i=0; i<=c+1; i++)
	{
		h[0][i]=-1;
		h[r+1][i]=-1;
	}//for i
	bfs();
	for (i=0; i<=r+1; i++)
	{
		for (j=0; j<=c+1; j++)
			printf("%ld ", h[i][j]);
		printf("\n");
	}//for i
	printf("%ld", bsearch());
	return 0;
}//main

long bsearch()
{
    long li=0, ls=r*c, lm;
	while (li<ls)
	{
		lm=(li+ls)/2;
		if (bfsm(lm))
			li=lm;
		else
			ls=lm;
	}//while
	return li;
}//bsearch

int bfsm(long m)
{
	long tx, ty, xx, yy;
	int i, j;
	for (i=0; i<=r+1; i++)
		for (j=0; j<=c+1; j++)
			fol[i][j]=0;
	p=0;
	u=0;
	qx[u]=xi;
	qy[u]=yi;
	fol[xi][yi]=1;
	while (p<=u)
	{
		tx=qx[p];
		ty=qy[p];
		p++;
		for (i=0; i<4; i++)
		{
			xx=tx+dx[i];
			yy=ty+dy[i];
			if ((h[xx][yy]>=0)&&(h[xx][yy]<=m)&&(!fol[xx][yy]))
			{
				if ((xx==xf)&&(yy==yf))
					return 1;
				fol[xx][yy]=1;
				u++;
				qx[u]=xx;
				qy[u]=yy;
			}//if
		}//for i
	}//while
	return 0;
}//bfsm

void bfs()
{
	long tx, ty, xx, yy;
	int i;
	while (p<=u)
	{
		tx=qx[p];
		ty=qy[p];
		p++;
		for (i=0; i<4; i++)
		{
			xx=tx+dx[i];
			yy=ty+dy[i];
			if (h[xx][yy]==-2)
			{
				h[xx][yy]=h[tx][ty]+1;
				u++;
				qx[u]=xx;
				qy[u]=yy;
			}//if
		}//for i
	}//while
}//bfs