Pagini recente » Cod sursa (job #339646) | Cod sursa (job #2507607) | Cod sursa (job #2503529) | Cod sursa (job #3201804) | Cod sursa (job #2889941)
#import<fstream>
#import<vector>
#import<algorithm>
#import<cmath>
#import<queue>
#import<unordered_set>
#import<string>
using namespace std;
ifstream cin("car.in");
ofstream cout("car.out");
int rez[501][501][10];
const int dir=8,inf=2e9;
int dc[]={ 1, 1, 1, 0,-1,-1,-1, 0};
int dl[]={-1, 0, 1, 1, 1, 0,-1,-1};
int n,m;
bool inside(const int x,const int y)
{
return (x>0 && x<=m && y>0 && y<=n);
}
bool ok[501][501];
int calculate_cost(int d1, int d2){
int p = abs(d2 - d1);
return min(p, 8 - p);
}
struct idk
{
int s,x,y,dir;
};
struct sortt
{
bool operator()(idk a,idk b)
{
return a.s>=b.s;;
}
};
main()
{
int xi,xf,yi,yf;
cin>>n>>m>>yi>>xi>>yf>>xf;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>ok[j][i];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
for(int k=0;k<dir;k++)
{
rez[j][i][k]=inf;
}
}
}
priority_queue<idk,vector<idk>,sortt>q;
for(int k=0;k<dir;k++)
{
rez[xi][yi][k]=0;
q.push({0,xi,yi,k});
}
while(!q.empty())
{
idk last=q.top();
q.pop();
if(rez[last.x][last.y][last.dir]!=last.s)
{
continue;
}
for(int i=0;i<8;i++)
{
int z=calculate_cost(i,last.dir);
int x=last.x+dc[i];
int y=last.y+dl[i];
if(!inside(x,y) || ok[x][y])
{
continue;
}
if(rez[x][y][i]>last.s+z)
{
rez[x][y][i]=last.s+z;
q.push({rez[x][y][i],x,y,i});
}
}
}
int minn=2e9;
for(int k=0;k<dir;k++)
{
minn=min(minn,rez[xf][yf][k]);
}
if(minn!=2e9)
{
cout<<minn;
}
else cout<<-1;
}