Pagini recente » Cod sursa (job #1285268) | Cod sursa (job #4544) | Cod sursa (job #1137047) | Cod sursa (job #2978064) | Cod sursa (job #3254769)
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <tuple>
#include <climits>
#define tuple tuple<int,int,int,int>
using namespace std;
ifstream fin ("car.in");
ofstream fout("car.out");
const vector<int> dx({-1, -1, -1, 0, 0, 1, 1, 1});
const vector<int> dy({-1, 0, 1, -1, 1, -1, 0, 1});
int n, m, s1, s2, f1, f2;
const int Max = 501;
vector<vector<int>> a(Max, vector<int>(Max)), c(Max, vector<int>(Max, INT_MAX));
bitset<Max> v[Max];
priority_queue<tuple, vector<tuple>, greater<tuple>> q;
bool verify(int x, int y)
{
return x >= 1 && y >= 1 && x <= n && y <= m && !a[x][y];
}
int calculate_cost(int d, int old_d)
{
if(old_d == d)
return 0;
if(old_d > 4)
old_d -= 5;
if(d > 4)
d -= 5;
if(old_d == d)
return 2;
int cost = abs(d - old_d);
return min(cost, 8 - cost);
}
int dijkstra(int x, int y)
{
c[x][y] = 0;
v[x][y] = 1;
for(int d = 0; d < 8; ++d)
{
int new_x = x + dx[d];
int new_y = y + dy[d];
if(verify(new_x, new_y))
{
c[new_x][new_y] = 0;
q.push({0, new_x, new_y, d});
}
}
while(!q.empty())
{
x = get<1>(q.top());
y = get<2>(q.top());
int old_d = get<3>(q.top());
q.pop();
if(v[x][y])
continue;
v[x][y] = 1;
for(int d = 0; d < 8; ++d)
{
int new_x = x + dx[d];
int new_y = y + dy[d];
int cost = calculate_cost(d, old_d);
if(verify(new_x, new_y) && c[x][y] + cost < c[new_x][new_y])
{
c[new_x][new_y] = c[x][y] + cost;
q.push({c[new_x][new_y], new_x, new_y, d});
}
}
}
if(c[f1][f2] != INT_MAX)
return c[f1][f2];
return -1;
}
int main()
{
fin >> n >> m >> s1 >> s2 >> f1 >> f2;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
fin >> a[i][j];
fout << dijkstra(s1, s2);
fin.close();
fout.close();
return 0;
}