#include <bits/stdc++.h>

using namespace std;

ifstream in("barbar.in");
ofstream out("barbar.out");

int di[4]={1,0,-1,0},dj[4]={0,1,0,-1};
int mat[1002][1002],viz[1002][1002],is,js,oi,oj,ans=-1;
queue<pair<int ,int> >q;
int n,m;
bool ok(int i,int j)
{
	if(i>=1&&i<=n&&j>=1&&j<=m)//&&mat[i][j]!=-2)
		return true;
	return false;
}


void firstlee()
{
	while(!q.empty())
	{
		int x=q.front().first;
		int y=q.front().second;
		q.pop();
		for(int k=0;k<4;k++)
		{
			int ii=x+di[k];
			int jj=y+dj[k];
			if(ok(ii,jj) && mat[ii][jj]==-1)
			{
				mat[ii][jj]=mat[x][y]+1;
				q.push(make_pair(ii,jj));
			}
		}
	}
}


int verify(int val)
{
	while(!q.empty())
		q.pop();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			viz[i][j]=0;
	viz[is][js]=1;
	if(mat[is][js]<val) return 0;
	q.push(make_pair(is,js));
	while(!q.empty())
	{
		int x=q.front().first;
		int y=q.front().second;
		q.pop();
		for(int k=0;k<4;k++)
		{
			int ii=x+di[k];
			int jj=y+dj[k];
			if(ok(ii,jj) && viz[ii][jj]==0 &&mat[ii][jj]>=val)
			{
				if(ii==oi&&jj==oj)  return 1;
				viz[ii][jj]=viz[x][y]+1;
				q.push(make_pair(ii,jj));
			}
		}
	}
	return 0;
}


void search()
{
	int dr=n*m;
	int st=0;
	while(st<=dr)
	{
		int mid=(st+dr)/2;
		if(verify(mid)==1)
		{
			ans=mid;
			st=mid+1;
		}
		else
			dr=mid-1;
	}
}

int main()
{	
	in>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			char c;
			in>>c;
			if(c=='.') mat[i][j]=-1;
			else if(c=='*') mat[i][j]=-2;
			else if(c=='D')
			{
				mat[i][j]=0;
				q.push(make_pair(i,j));
			}
			else if(c=='I')
			{
				is=i;
				js=j;
				mat[i][j]=-1;
			}
			else if(c=='O')
			{
				oi=i;
				oj=j;
				mat[i][j]=-1;
			}
		}
	firstlee();
	search();
	cout<<endl;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			cout<<mat[i][j]<<" ";
		cout<<"\n";
	}
	out<<ans<<"\n";
	return 0;
}