Pagini recente » Cod sursa (job #1557391) | Cod sursa (job #3154569) | Cod sursa (job #2557024) | Cod sursa (job #1745857) | Cod sursa (job #2637155)
#include<bits/stdc++.h>
using namespace std;
#define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll
ifstream fin("car.in"); ofstream fout("car.out");
#define cin fin
#define cout fout
int t, n, m, mat[510][510];
pii f, s;
int d[510][510], dir[510][510];
bool v[510][510];
multiset<pair<int, pii>> q;
int cost[200];
void vicinity(pair<int, pii> s){
vector<int> Y={-1, 1,0, 0, -1, 1, -1, 1};
vector<int> X={1, 1, 1, -1, -1, -1, 0, 0};
vector<int> D={-45, 45, 0, 180, -135, 135, -90, 90};
for(int g=0; g<D.size(); g++){
int x=max( (int)1, min(m, s.sc.sc+X[g]) ), y=max( (int)1, min(n, s.sc.ft+Y[g]) );
if( (v[y][x]==false) && mat[y][x]==0){
if(dir[s.sc.ft][s.sc.sc]==-1){
dir[y][x]=D[g];
q.insert(mp(0, mp(y, x)) ); d[y][x]=0;
}
else{
auto it=q.find(mp(d[y][x], mp(y, x)) );
int ch=abs(D[g]-dir[s.sc.ft][s.sc.sc]);
if(ch!=180){
ch%=180;
}
int dist=d[s.sc.ft][s.sc.sc]+cost[ch];
if(it!=q.end()){
q.erase(it);
if(dist<d[y][x]){
dir[y][x]=D[g];
d[y][x]=dist;
}
}
else{
d[y][x]=dist;
dir[y][x]=D[g];
}
q.insert(mp(d[y][x], mp(y, x)));
}
}
}
}
void dijkstra(pii src){
q.insert(mp(0, src) );
v[src.ft][src.sc]=true;
dir[src.ft][src.sc]=-1;
while(!q.empty()){
pair<int, pii> f=(*q.begin()); q.erase(q.begin());
v[f.sc.ft][f.sc.sc]=true;
vicinity(f);
}
}
int32_t main(){
INIT
cin>>n>>m;
cin>>f.ft>>f.sc>>s.ft>>s.sc;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
cin>>mat[i][j];
}
}
cost[0]=0; cost[45]=1; cost[90]=2; cost[135]=3; cost[180]=4;
dijkstra(f);
int y=s.ft; int x=s.sc;
if(v[y][x]==true && mat[y][x]==0 && mat[f.ft][f.sc]==0){
cout<<d[y][x];
}
else{
cout<<-1;
}
/*cout<<"\n";
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
cout<<d[i][j]<<" ";
}
cout<<"\n";
}*/
return 0;
}