Pagini recente » Cod sursa (job #567600) | Cod sursa (job #2918908) | Cod sursa (job #497476) | Cod sursa (job #2802434) | Cod sursa (job #2413395)
#include <fstream>
#include <queue>
#define inf 1000000000
#include<algorithm>
using namespace std;
ifstream fin ("car.in");
ofstream fout("car.out");
int di[8]={1,1,0,-1,-1,-1,0,1};
int dj[8]={0,1,1,1,0,-1,-1,-1};
struct punct{int x;int y;int d;} aux,p;
queue<punct> l,q;
int i,j,h,x1,x2,y1,y2,n,m,a[512][512],d[512][512][10];
int main ()
{
fin>>n>>m;
fin>>x1>>y1>>x2>>y2;
for(i=1;i<=n;i++) for(j=1;j<=m;j++){fin>>a[i][j];a[i][j]=1-a[i][j];for(h=0;h<=7;h++) d[i][j][h]=inf;}
for(i=0;i<=7;i++)
{
aux.x=x1;aux.y=y1;aux.d=i;
d[x1][y1][i]=0;
q.push(aux);
}
while(!q.empty())
{
while(!q.empty())
{
aux=q.front();q.pop();
// fout<<aux.x<<" "<<aux.y<<" "<<aux.d<<"\n";
if(aux.x==x2&&aux.y==y2){fout<<d[aux.x][aux.y][aux.d];return 0;}
p=aux;p.x+=di[p.d];p.y+=dj[p.d];
if(a[p.x][p.y]==1&&d[p.x][p.y][p.d]>d[aux.x][aux.y][aux.d])
{
d[p.x][p.y][p.d]=d[aux.x][aux.y][aux.d];
q.push(p);
}
p=aux;p.d=(p.d+1)%8;
if(d[p.x][p.y][p.d]>d[aux.x][aux.y][aux.d]+1)
{
d[p.x][p .y][p.d]=d[aux.x][aux.y][aux.d]+1;
l.push(p);
}
p=aux;p.d-=1;if(p.d==-1) p.d=7;
if(d[p.x][p.y][p.d]>d[aux.x][aux.y][aux.d]+1)
{
d[p.x][p.y][p.d]=d[aux.x][aux.y][aux.d]+1;
l.push(p);
}
}
while(!l.empty())
{
q.push(l.front());
l.pop();
}
}
fout<<-1;
return 0;
}