Pagini recente » Cod sursa (job #2814903) | Cod sursa (job #132502)
Cod sursa(job #132502)
#include <fstream.h>
#include <string.h>
#define MAX 1005
ifstream fin ("barbar.in");
ofstream fout ("barbar.out");
const int x[4]={-1,0,0,1};
const int y[4]={0,-1,1,0};
int n,a[MAX][MAX],m,xi,yi,xf,yf,mat[MAX][MAX];
void citire()
{
fin>>n>>m;
char s[1010];
fin.getline(s,1010);
for (int i=1;i<=n;i++)
{
fin.getline (s,1010);
for (int j=1;j<strlen(s)+1;j++)
{
if (s[j-1]=='.')
a[i][j]=-1;
else
if (s[j-1]=='*')
a[i][j]=-2;
else
if (s[j-1]=='D')
a[i][j]=0;
else
if (s[j-1]=='I')
{
a[i][j]=-3;
xi=i;
yi=j;
}
else
if (s[j-1]=='O')
{
a[i][j]=-3;
xf=i;
yf=j;
}
}
}
}
int max(int a,int b)
{
if (a<b)
return a;
return b;
}
void umplu()
{
int p;
for (p=0;p<n+1;p++)
{
a[p][0]=-2;
a[p][m+1]=-2;
}
for (p=0;p<m+1;p++)
{
a[0][p]=-2;
a[n+1][p]=-2;
}
memset(mat,999,sizeof(mat));
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (a[i][j]==0)
{
int ii=i,jj=j;
for (int k=0;k<4;k++)
{
int nr=0;
ii=i;
jj=j;
while (a[ii][jj]!=-2)
{
mat[ii][jj]=max(mat[ii][jj],nr);
nr++;
ii+=x[k];
jj+=y[k];
}
}
}
}
int min(int a,int b)
{
if (a<b)
return a;
return b;
}
void fac()
{
int xx[1000000],yy[1000000];
int nr=1;
xx[0]=xi;
yy[0]=yi;
int nr1=0;
while (nr){
nr1=0;
for (int i=0;i<nr;i++)
for (int k=0;k<4;k++)
if ( a[xx[i] +x[k]][yy[i] +y[k]] !=-2)
{
if (nr<999990){
mat[xx[i] +x[k]][yy[i] +y[k]]=min(mat[xx[i] +x[k]][yy[i] +y[k]],mat[xx[i]][yy[i]]);
xx[nr]=xx[i]+x[k];
yy[nr]=yy[i]+y[k];
nr++;
}
else
{
mat[xx[i] +x[k]][yy[i] +y[k]]=min(mat[xx[i] +x[k]][yy[i] +y[k]],mat[xx[i]][yy[i]]);
xx[nr1]=xx[i]+x[k];
yy[nr1]=yy[i]+y[k];
nr1++;
}
}
nr=nr1;
}
}
int main ()
{
citire();
umplu();
fac();
if (mat[xf][yf]==9)
fout<<-1<<"\n";
else
fout<<mat[xf][yf]<<"\n";
fout.close();
fin.close();
return 0;
}