Pagini recente » Cod sursa (job #3309871) | Cod sursa (job #3351523) | Cod sursa (job #3310948) | Cod sursa (job #3347316) | Cod sursa (job #3342368)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
const int INF=1e9;
struct Stare{
int drum,directie;
int linie,coloana;
};
struct ComparaCost {
bool operator()(const Stare& a, const Stare& b) {
return a.drum > b.drum; // Din nou, inversam pentru min-heap
}
};
int N,M,Si,Sj,Fi,Fj,mat[505][505],d[505][505][8];
int curbe[5]={0,1,2,3,4};
int dir_i[8]={-1,-1,-1,0,1,1,1,0};
int dir_j[8]={-1,0,1,1,1,0,-1,-1};
priority_queue < Stare, vector<Stare>, ComparaCost > pq;
void citire(){
fin>>N>>M>>Si>>Sj>>Fi>>Fj;
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
fin>>mat[i][j];
}
}
memset(d, 0x3f, sizeof(d));
}
void dijk(int start_i, int start_j){
for(int i=0;i<8;i++){
int lin=start_i+dir_i[i];
int col=start_j+dir_j[i];
if((lin>=1 && lin<=N && col>=1 && col<=M) && mat[lin][col]==0) {
Stare nod;
nod.drum=0;
nod.linie=start_i;
nod.coloana=start_j;
nod.directie=i;
d[start_i][start_j][i]=0;
pq.push(nod);
}
}
while(!pq.empty()){
Stare x=pq.top();
int dr=x.drum;
int dir=x.directie;
int i=x.linie,j=x.coloana;
pq.pop();
for(int k=0;k<8;k++){
int lin=i+dir_i[k];
int col=j+dir_j[k];
if((lin>=1 && lin<=N && col>=1 && col<=M) && mat[lin][col]==0) {
int next_dir=min(abs(dir-k),(8-abs(dir-k)));
int next_cost=d[i][j][dir]+next_dir;
if(next_cost<d[lin][col][k]){
d[lin][col][k]=next_cost;
Stare next;
next.drum=d[lin][col][k];
next.directie=k;
next.linie=lin;
next.coloana=col;
pq.push(next);
}
}
}
}
}
int main()
{
citire();
dijk(Si,Sj);
int minim=INF ,minim_i;
for(int i=0;i<8;i++){
if(d[Fi][Fj][i]<minim){
minim_i=i;
minim=d[Fi][Fj][i];
}
}
fout<<d[Fi][Fj][minim_i];
return 0;
}