Pagini recente » Cod sursa (job #261759) | Cod sursa (job #1244813) | Cod sursa (job #1255422) | Cod sursa (job #2082064) | Cod sursa (job #1837404)
#include<fstream>
#include<iostream>
using namespace std;
ifstream f("lee.in");
ofstream g("lee.out");
int t[1001][1001],a[1001][1001],c,pas,is,js,id,jd,x,y,xx,yy,n,m,inf, drumx[1001],drumy[1001],k;
const int dx[]= {-1,-1,0,+1,+1,+1,0,-1};
const int dy[]= {0,+1,+1,+1,0,-1,-1,-1};
int main ()
{ int i,j,k,l;
f>>n>>m;
f>>is>>js>>id>>jd;
for(i=1; i<=n; i++)
for(j=1; j<=m; j++)
f>>t[i][j];
inf=n*m+1;
for(i=1; i<=n; i++)
for(j=1; j<=m; j++)
a[i][j]=m*n+1;
if((t[is][js]==1)||(t[id][jd]==1)) g<<"Nu exista solutie"<<endl;
else
{
a[is][js]=0;
pas=0;
c=1;
while(c)
{
c=0;
for(x=1; x<=n; x++)
for(y=1; y<=m; y++)
{
if(a[x][y]==pas)
for(i=0; i<8; i++)
{
xx=x+dx[i];
yy=y+dy[i];
if((1<=xx && xx<=n) && (1<=yy && yy<=m) && t[xx][yy]!=1 && a[xx][yy]>pas)
{
a[xx][yy]=pas+1;
c=1;
}
}
if(a[id][jd]!=inf)
{
x=n;
y=m;
c=0;
}
}
pas++;
} //sf. corp while
if(a[id][jd]==inf) g<<"Nu exista solutie"<<endl;
else g<<a[id][jd]<<endl;
}
// afisare drum
// pornesc de la sfarsit spre inceput
x=id;
y=jd;
// in vectorii drumx[] si drumy[] retin coordonatele
k=1;
drumx[k]=id;
drumy[k]=jd;
while(x!=is&&y!=js)
for(i=0; i<8; i++)
{
xx=x-dx[i];
yy=y-dy[i];
if(a[xx][yy]+1==a[x][y])
{
k++;
drumx[k]=xx;
drumy[k]=yy;
// actualizez
x=xx;
y=yy;
break; // opresc for
}
}
for(i=k; i>=1; i--)
g<<drumx[i]<<" "<<drumy[i]<<'\n';
return 0;
}