Pagini recente » Cod sursa (job #666726) | Cod sursa (job #1429271) | Cod sursa (job #1550619) | Cod sursa (job #1043324) | Cod sursa (job #2166780)
#include <bits/stdc++.h>
#define INFILE "car.in"
#define OUTFILE "car.out"
#define x first
#define y second
#define lung first
#define mod second.first
#define poz second.second
using namespace std;
const int NMAX=510;
typedef array<array<int,NMAX>,NMAX> Map;
typedef pair<int,int> coord;
ifstream in(INFILE);
ofstream out(OUTFILE);
const int nrdir=8;
const int INF=INT_MAX;
int dlin[nrdir+1]={0,-1,-1,0,1,1,1,0,-1};
int dcol[nrdir+1]={0,0,1,1,1,0,-1,-1,-1};
int Cost(int reper,int dir){
int val=abs(reper-dir);
if(val>nrdir/2)
return nrdir-val;
return val;
}
array<Map,nrdir+1> dist;
Map Harta;
int N,M;
int Si,Sj,Fi,Fj;
void AfisMp(Map&mp){
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
if(mp[i][j]==INF){
cout<<setw(2)<<-1<<" ";
}
else cout<<setw(2)<<mp[i][j]<<" ";
}
cout<<"\n";
}
cout<<"~~~\n";
}
void Read(){
in>>N>>M;
in>>Si>>Sj>>Fi>>Fj;
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
in>>Harta[i][j];
}
}
//cout<<N<<" "<<M<<endl;
//AfisMp(Harta);
}
bool OutOfBoundries(int lin,int col){
if(lin<1||col<1||lin>N||col>M)
return true;
if(Harta[lin][col]==1)
return true;
return false;
}
void Dijkstra(){
typedef pair<int,pair<int,coord>> superData;
priority_queue<superData,vector<superData>,greater<superData>> coada;
for(int k=1;k<=nrdir;k++){
coada.push({0,{k,{Si,Sj}}});
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
dist[k][i][j]=INF;
}
}
dist[k][Si][Sj]=0;
}
while(!coada.empty()){
int lin=coada.top().poz.x;
int col=coada.top().poz.y;
int reper=coada.top().mod;
int dst=coada.top().lung;
coada.pop();
for(int k=1;k<=nrdir;k++){
int nlin=lin+dlin[k];
int ncol=col+dcol[k];
//cout<<nlin<<" "<<ncol<<" "<<k<<"\n";
if(OutOfBoundries(nlin,ncol)) continue;
int cost=Cost(reper,k);
if(dist[k][nlin][ncol]>dst+cost){
dist[k][nlin][ncol]=dst+cost;
//
//cout<<dist[k][nlin][ncol]<<" "<<k<<" "<<nlin<<" "<<ncol<<"\n";
coada.push({dst+cost,{k,{nlin,ncol}}});
}
}
}
int Mn=INF;
for(int k=1;k<=nrdir;k++){
//AfisMp(dist[k]);
Mn=min(Mn,dist[k][Fi][Fj]);
}
if(Mn==INF){
out<<-1<<"\n";
}
else{
out<<Mn;
}
}
int main(){
Read();
Dijkstra();
return 0;
}