Cod sursa(job #792075)
#include<fstream>
#include<vector>
#include<queue>
#define inf 10000000
using namespace std;
ofstream g("barbar.out");
int n,m,i,j,d[1001][1001],a[1001][1001],xi,yi,xf,yf,st,dr,mij,rez=0;
char x;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
struct coord
{
int i,j;
};
queue<coord>q;
void lee()
{
int x,y,xx,yy,i;
while(!q.empty())
{
x=q.front().i;
y=q.front().j;
for(i=0;i<4;i++)
{
xx=x+dx[i];
yy=y+dy[i];
if(d[xx][yy]>d[x][y]+1&&xx<=n&&yy<=m&&xx>0&&yy>0)
{
d[xx][yy]=d[x][y]+1;
q.push((coord){xx,yy});
}
}
q.pop();
}
}
int lee1(int val)
{
int x,y,xx,yy,i;
q.push((coord){xi,yi});
while(!q.empty())
{
x=q.front().i;
y=q.front().j;
for(i=0;i<4;++i)
{
xx=x+dx[i];
yy=y+dy[i];
if(d[xx][yy]>=val&&xx<=n&&yy<=m&&xx>0&&yy>0&&a[xx][yy]!=val&&d[xx][yy]!=-1)
{
a[xx][yy]=val;
q.push((coord){xx,yy});
if(xx==xf&&yy==yf)
{
while(!q.empty())
q.pop();
return 1;
}
}
}
q.pop();
}
return 0;
}
int main()
{
ifstream f("barbar.in");
f>>n>>m;
for(i=1;i<=n;++i)
for(j=1;j<=m;++j)
{
f>>x;
if(x=='.')
a[i][j]=d[i][j]=inf;
else
if(x=='*')
a[i][j]=d[i][j]=-1;
else
if(x=='I')
xi=i,yi=j;
else
if(x=='O')
{
d[i][j]=a[i][j]=inf;
xf=i,yf=j;
}
else
if(x=='D')
{
q.push((coord){i,j});
d[i][j]=0;
}
}
lee();
st=1, dr=d[xf][yf];
while(st<dr)
{
mij=(st+dr)/2;
if(lee1(mij))
{
st=mij+1;
if(mij>rez)
rez=mij;
}
else
dr=mij-1;
}
if(rez)
g<<rez;
else
g<<-1;
return 0;
}