Pagini recente » Cod sursa (job #832735) | Cod sursa (job #1025467)
#include<iostream>
#include<fstream>
using namespace std;
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
int r,c, sx, sy, fx, fy, q1[1000], q2[1000];
char a;
int b[1000][1000], ok=0, d[1000][1000];
bool fol[1000][1000];
void BF(int u, int v)
{
int k, si, sf, x, y, max=-1; si=sf=0;
q1[0]=u;
q2[0]=v;
while(si<=sf)
{
x=q1[si];
y=q2[si];
si++;
for( k = 0; k <= 3 ; k ++)
{
if((b[x+dx[k]][y+dy[k]]==0) && x+dx[k]<r && y+dy[k]<c && x+dx[k]>=0 &&y+dy[k]>=0)
{
b[x+dx[k]][y+dy[k]]=b[x][y]+1;
if(max<b[x+dx[k]][y+dy[k]])
max=b[x+dx[k]][y+dy[k]];
sf++;
q1[sf]=x+dx[k];
q2[sf]=y+dy[k];
}
}
}
}
void BFF(int x, int y)
{
int k;
for(k=0; k <=3; k++)
{
if((d[x+dx[k]][y+dy[k]]>0)&& d[x][y]>d[x+dx[k]][y+dy[k]] && x+dx[k]<r && y+dy[k]<c && x+dx[k]>=0 &&y+dy[k]>=0)
{
int t=min(b[x+dx[k]][y+dy[k]], d[x][y]);
t=max(t, d[x+dx[k]][y+dy[k]]);
d[x+dx[k]][y+dy[k]]=t;
if(x+dx[k]==fx && y+dy[k]==fy)
ok=1;
BFF(x+dx[k], y+dy[k]);
}
}
}
int main()
{
ifstream f("barbar.in");
ofstream g("barbar.out");
int i, j;
f>>r>>c;
for(i = 0; i < r; i++)
for(j = 0; j < c; j ++)
{
f>>a;
if(a=='*')
b[i][j]=-1;
if(a=='.')
b[i][j]=0;
if(a=='D')
b[i][j]=-2;
if(a=='I')
sx=i, sy=j, b[i][j]=0;
if(a=='O')
fx=i, fy=j, b[i][j]=0;
}
for(i=0; i<r; i++)
for(j=0; j<c; j++)
if(b[i][j] == -2)
{
BF(i, j);
}
for(i=0;i<r;i++)
for(j=0;j<c;j++)
d[i][j]=1;
d[sx][sy]=b[sx][sy];
BFF(sx,sy);
g<<d[fx][fy];
}