Pagini recente » Cod sursa (job #1672452) | Cod sursa (job #2102175) | Cod sursa (job #173228) | Cod sursa (job #2298672) | Cod sursa (job #2260502)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
const int Nmax=505;
const int oo=2e9;
int n,m,xi,yi,xf,yf;
int a[Nmax][Nmax];
int drum[Nmax][Nmax][10];
int dx[] = {-1,-1,0,1,1,1,0,-1};
int dy[] = {0,1,1,1,0,-1,-1,-1};
struct Coada
{
int x,y,cost,dir;
};
queue<Coada>Q;
queue<Coada>q;
void Init()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=0;k<8;k++)
drum[i][j][k]=oo;
}
inline bool Verificare(int x,int y)
{
return x>=1 && x<=n && y>=1 && y<=m && a[x][y]==0;
}
void Build()
{
for(int k=0;k<8;k++)
Q.push({xi,yi,0,k});
Coada x,y;
while(!Q.empty())
{
while(!Q.empty())
{
x=Q.front();
Q.pop();
y.cost=x.cost;
y.dir=x.dir;
y.x=x.x+dx[x.dir];
y.y=x.y+dy[x.dir];
if(Verificare(y.x,y.y) && drum[y.x][y.y][y.dir]>y.cost)
{
drum[y.x][y.y][y.dir]=y.cost;
Q.push(y);
}
y.x=x.x;
y.y=x.y;
y.cost=x.cost+1;
y.dir=x.dir+1;
if(y.dir==8)y.dir=0;
if(Verificare(y.x,y.y) && drum[y.x][y.y][y.dir]>y.cost)
{
drum[y.x][y.y][y.dir]=y.cost;
q.push(y);
}
y.dir=x.dir-1;
if(y.dir<0)y.dir=7;
if(Verificare(y.x,y.y) && drum[y.x][y.y][y.dir]>y.cost)
{
drum[y.x][y.y][y.dir]=y.cost;
q.push(y);
}
}
while(!q.empty())
{
x=q.front();
q.pop();
Q.push(x);
}
}
}
int main()
{
fin>>n>>m>>xi>>yi>>xf>>yf;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
fin>>a[i][j];
Init();
Build();
int minim=oo;
for(int i=0;i<8;i++)
minim=min(minim,drum[xf][yf][i]);
if(minim==oo)fout<<"-1\n";
else fout<<minim<<"\n";
fin.close();
fout.close();
return 0;
}