Cod sursa(job #96178)
#include<stdio.h>
long int a[1100][1100], n, m, x1, y1, x2, y2, nr, b[1100][1100];
long int dx[4]={0,1,0,-1}, dy[4]={1,0,-1,0};
typedef struct
{
long int x, y;
} Coada;
Coada c[2000000];
void citire()
{
freopen("barbar.in","r",stdin);
freopen("barbar.out","w",stdout);
scanf("%ld %ld",&n,&m);
long int i, j;
char x;
scanf("\n");
for (i=1; i<=n; i++)
{
for (j=1; j<=m; j++)
{
scanf("%c",&x);
switch(x)
{
case '.' : {a[i][j]=-1; break;}
case '*' : {a[i][j]=-2; break;}
case 'D' : {a[i][j]=0; c[++nr].x=i; c[nr].y=j;break;}
case 'I' : {x1=i, y1=j, a[i][j]=-1; break;}
case 'O' : {x2=i, y2=j, a[i][j]=-1; break;}
}
}
scanf("\n");
}
for (i=1; i<=n; i++) a[i][0]=a[i][m+1]=-2;
for (i=1; i<=m; i++) a[0][i]=a[n+1][i]=-2;
}
void parcurg()
{
long int p, u, x, y, i;
p=1;
u=nr;
while (p<=u)
{
for (i=0; i<4; i++)
{
x=c[p].x+dx[i];
y=c[p].y+dy[i];
if (a[x][y]==-1)
{
u++;
c[u].x=x;
c[u].y=y;
a[x][y]=a[c[p].x][c[p].y]+1;
}
}
p++;
}
}
int verif (int dist)
{
long int p, u, x, y, i, j;
p=1;
u=1;
c[1].x=x1; c[1].y=y1;
if (dist==0)
for (i=1; i<=n; i++)
for (j=1; j<=m; j++) b[i][j]=1;
while (p<=u)
{
for (i=0; i<4; i++)
{
x=c[p].x+dx[i];
y=c[p].y+dy[i];
if (a[x][y]>=dist && b[x][y]!=dist)
{
if (x==x2 && y==y2) return 1;
u++;
c[u].x=x;
c[u].y=y;
b[x][y]=dist;
}
}
p++;
}
return 0;
}
/*
int caut()
{
int p, u, m;
p=0; u=1010;
m=(p+u)/2;
while (p<u)
{
if (verif(m) && !verif(m+1)) return m;
else if (verif(m) && verif(m+1)) {p=m; m=(p+u)/2;}
else {u=m; m=(p+u)/2;}
}
return -1;
}
*/
int main()
{
citire();
parcurg();
long int i=a[x1][y1];
while (!verif(i) && i>=0) i--;
printf("%ld",i);
return 0;
}