Pagini recente » Cod sursa (job #3360133) | Cod sursa (job #3360144) | Cod sursa (job #3360813) | Cod sursa (job #3360145) | Cod sursa (job #3360294)
#include <iostream>
#pragma GCC optimize("O3,unroll-loops")
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <iomanip>
#include <numeric>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
//#define int long long
//#define int short
using namespace std;
const int nmax = 500;
const int dirmax = 8;
const int inf = 1e9;
int n, m, v[nmax + 5][nmax + 5], d[nmax + 5][nmax + 5][dirmax], istart, jstart, iend, jend;
int dx[] = {0, -1, -1, -1, 0, 1, 1, 1};
int dy[] = {-1, -1, 0, 1, 1, 1, 0, -1};
struct Car{
int i;
int j;
int dir;
int dis;
};
struct cmp{
bool operator()(const Car& a, const Car& b)const{
return a.dis > b.dis;
}
};
bool inm(int i, int j){
if (i >= 1 && i <= n && j >= 1 && j <= m){
return true;
}
return false;
}
void dijkstra(){
priority_queue<Car, vector<Car>, cmp> pq;
for (int dir = 0; dir < 8; dir++){
d[istart][jstart][dir] = 0;
pq.push({istart, jstart, dir, 0});
}
while (!pq.empty()){
Car currcar = pq.top(); pq.pop();
if (currcar.dis > d[currcar.i][currcar.j][currcar.dir]){
continue;
}
for (int dir = 0; dir < 8; dir++){
int ni = currcar.i + dx[dir];
int nj = currcar.j + dy[dir];
int ndis = currcar.dis + ((abs(currcar.dir - dir) > 4) ? 8 - abs(currcar.dir - dir) : abs(currcar.dir - dir));
if (inm(ni, nj) && !v[ni][nj] && ndis < d[ni][nj][dir]){
d[ni][nj][dir] = ndis;
pq.push({ni, nj, dir, ndis});
}
}
}
}
int GetSmallestDis(int i, int j){
int mn = inf;
for (int dir = 0; dir < 8; dir++){
mn = min(mn, d[i][j][dir]);
}
return mn;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
freopen("car.in", "r", stdin);
freopen("car.out", "w", stdout);
cin>>n>>m>>istart>>jstart>>iend>>jend;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
cin>>v[i][j];
for (int dir = 0; dir < 8; dir++){
d[i][j][dir] = inf;
}
}
}
dijkstra();
cout<<GetSmallestDis(iend, jend);
}