Pagini recente » Cod sursa (job #197346) | Cod sursa (job #72741) | Cod sursa (job #1030669) | Cod sursa (job #3000026) | Cod sursa (job #2820573)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
int n,m,si,sj,fi,fj;
int a[505][505],cost[8][8],dp[8][505][505];
int dx[8]={-1,0,1,1,1,0,-1,-1};
int dy[8]={1,1,1,0,-1,-1,-1,0};
/// 670
/// 5 1
/// 432
struct atom
{
int d,x,y,c;
bool operator < (const atom b) const
{
return c>b.c;
}
};
priority_queue <atom> pq;
void update(atom x)
{
if(dp[x.d][x.x][x.y]>x.c)
{
dp[x.d][x.x][x.y]=x.c;
pq.push(x);
}
}
int main()
{
fin>>n>>m>>si>>sj>>fi>>fj;
int i,j;
for(i=1; i<=n; i++)
for(j=1; j<=m; j++)
fin>>a[i][j];
for(i=0; i<8; i++)
{
for(j=0; j<8; j++)
{
int t=(j-i+8)%8;
cost[i][j]=t%5;
}
}
for(i=1; i<=n; i++)
for(j=1; j<=m; j++)
for(int d=0; d<8; d++)
dp[d][i][j]=1e9;
dp[7][si][sj]=0;
pq.push({7,si,sj,0});
while(!pq.empty())
{
atom x=pq.top(); pq.pop();
if(dp[x.d][x.x][x.y]<x.c)
continue;
if(x.x==fi && x.y==fj)
{
fout<<x.c<<"\n";
return 0;
}
for(int dir=0; dir<8; dir++)
{
int iv=x.x+dx[dir],jv=x.y+dy[dir];
if(iv<1 || iv>n || jv<1 || jv>m)
continue;
if(a[iv][jv]==1)
continue;
atom y;
y.d=dir; y.x=iv; y.y=jv; y.c=x.c+cost[x.d][dir];
update(y);
}
}
fout<<"-1\n";
return 0;
}