Pagini recente » Cod sursa (job #3125393) | Cod sursa (job #3276597)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
const int dx[]= {-1,-1,0,1,1,1,0,-1};
const int dy[]= {0,1,1,1,0,-1,-1,-1};
const int Nmax=505;
int a[Nmax][Nmax];
bool viz[Nmax][Nmax][10];
struct celula
{
int x,y;
int val;
int dir;
bool operator <(const celula cmp) const
{
return val>cmp.val;
}
};
int n,m;
bool inmat(int i,int j)
{
return (1<=i && i<=n && 1<=j && j<=m);
}
int main()
{
fin>>n>>m;
int sx,sy,fx,fy;
fin>>sx>>sy>>fx>>fy;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
fin>>a[i][j];
}
}
priority_queue<celula> pq;
pq.push({sx,sy,0,-1});
while(!pq.empty())
{
int i=pq.top().x;
int j=pq.top().y;
int d=pq.top().dir;
int cost=pq.top().val;
pq.pop();
if(a[i][j]==1) continue;
if(viz[i][j][d]) continue;
viz[i][j][d]=0;
if(i==fx && j==fy)
{
fout<<cost<<'\n';
return 0;
}
for(int k=0; k<8; k++)
{
int newi=i+dx[k];
int newj=j+dy[k];
int turn;
/// 0 degree "turn"
if(abs(k-d)==0 || d==-1) turn=0;
/// 45 degree turn
else if(abs(k-d)==1 || abs(k-d)==7) turn=1;
///90 degree turn
else if(abs(k-d)==2 || abs(k-d)==6) turn=2;
/// 135 degree turn
else if(abs(k-d)==3 || abs(k-d)==5) turn=3;
///180 degree turn
else if(abs(k-d)==4) turn=4;
if(inmat(newi,newj) && !viz[newi][newj][k])
{
pq.push({newi,newj,cost+turn,k});
}
}
}
fout<<-1<<'\n';
return 0;
}