Pagini recente » Cod sursa (job #149245) | Cod sursa (job #1273922) | Cod sursa (job #942333) | Cod sursa (job #1975101) | Cod sursa (job #184284)
Cod sursa(job #184284)
#include <stdio.h>
#define MAXN 1100
struct coord
{
int x,y;
};
int dx[5]={1,-1,0,0};
int dy[5]={0,0,-1,1};
int v[MAXN][MAXN];
int v2[MAXN][MAXN];
coord dragons[10*MAXN*MAXN];
int Sx,Sy,Ex,Ey,n,m,D=0;
void citire()
{
char s[MAXN*2]; int i,j;
fgets(s,32,stdin);
n=0; m=0; j=0;
while (s[j]>='0' && s[j]<='9')
n=n*10+s[j++]-'0';
j++;
while (s[j]>='0' && s[j]<='9')
m=m*10+s[j++]-'0';
for (i=1; i<=n; ++i)
{
fgets(s,MAXN*2,stdin);
for (j=1; j<=n; ++j)
{
if (s[j-1]=='.')
v[i][j]=0;
if (s[j-1]=='D')
{
v[i][j]=-1;
dragons[D].x=i;
dragons[D].y=j;
D++;
}
if (s[j-1]=='*')
v[i][j]=-4;
if (s[j-1]=='I')
{
v[i][j]=0;
Sx=i; Sy=j;
}
if (s[j-1]=='O')
{
v[i][j]=0;
Ex=i; Ey=j;
}
}
}
for (i=0; i<=m+1; ++i)
{
v[0][i]=-4;
v[n+1][i]=-4;
}
for (i=0; i<=n+1; ++i)
{
v[i][0]=-4;
v[i][m+1]=-4;
}
}
void wtf()
{
int i,j;
for (i=0; i<D; ++i)
for (j=0; j<4; ++j)
if (v[ dragons[i].x + dx[j] ] [ dragons[i].y + dy[j] ] == 0)
{
v[ dragons[i].x + dx[j] ] [ dragons[i].y + dy[j] ] = v[ dragons[i].x ] [ dragons[i].y ] +1;
if (v[ dragons[i].x + dx[j] ] [ dragons[i].y + dy[j] ] == 0)
v[ dragons[i].x + dx[j] ] [ dragons[i].y + dy[j] ]++;
dragons[D].x=dragons[i].x+ dx[j];
dragons[D].y=dragons[i].y+ dy[j];
D++;
}
}
inline int min(int a, int b)
{
if (a>b)
return b;
return a;
}
void reset()
{
int i;
for (i=0; i<MAXN*MAXN; ++i)
{
dragons[i].x=0;
dragons[i].y=0;
}
D=0;
}
void wtf2()
{
int k,i,j;
i=0;
while (i<D)
{
for (j=0; j<4; ++j)
if (dragons[i].x+dx[j]>=1 && dragons[i].x+dx[j]<=n &&
dragons[i].y+dy[j]>=1 && dragons[i].y+dy[j]<=m )
if (v[ dragons[i].x + dx[j] ] [ dragons[i].y + dy[j] ] >= 0)
{
k=min( v2[dragons[i].x][dragons[i].y] , v[ dragons[i].x + dx[j] ][ dragons[i].y + dy[j] ] );
if (v2[ dragons[i].x + dx[j] ][ dragons[i].y + dy[j] ] == 0 || v2[ dragons[i].x + dx[j] ][ dragons[i].y + dy[j] ] < k)
if ( !(dragons[i].x + dx[j] ==Sx && dragons[i].y + dy[j] == Sy) )
{
v2[ dragons[i].x + dx[j] ][ dragons[i].y + dy[j] ]=k;
if ( !(dragons[i].x + dx[j] ==Ex && dragons[i].y + dy[j] == Ey) )
{
dragons[D].x = dragons[i].x+ dx[j];
dragons[D].y = dragons[i].y+ dy[j];
D++;
}
}
}
i++;
}
}
int main()
{
freopen("barbar.in","r",stdin);
freopen("barbar.out","w",stdout);
citire();
wtf();
reset();
dragons[0].x=Sx;
dragons[0].y=Sy; D=1;
v2[Sx][Sy]=v[Sx][Sy];
wtf2();
if (v2[Ex][Ey])
printf("%d\n",v2[Ex][Ey]);
else
printf("-1\n");
fclose(stdin);
fclose(stdout);
return 0;
}