Pagini recente » Cod sursa (job #2509734) | Cod sursa (job #692262) | Cod sursa (job #456011) | Cod sursa (job #666281) | Cod sursa (job #2516243)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
const int NMax = 500, DistMax = 5e5, oo = 1e9;
int dl[8] = {0, -1, -1, -1, 0, 1, 1, 1}, dc[8] = {-1, -1, 0, 1, 1, 1, 0, - 1}, Cost[8][8];
int N, M, l1, c1, l2, c2, D[NMax + 5][NMax + 5][8];
bool Access[NMax + 5][NMax + 5];
struct cell{int l, c, o;};
vector <cell> Bucket[DistMax + 5];
int main()
{
fin >> N >> M >> l1 >> c1 >> l2 >> c2;
for(int i = 1; i <= N; i++)
for(int j = 1; j <= M; j++)
{
fin >> Access[i][j];
for(int t = 0; t < 8; t++)
D[i][j][t] = oo;
}
for(int t = 0; t < 8; t++)
{
D[l1][c1][t] = 0;
Bucket[0].push_back({l1, c1, t});
}
for(int o = 0; o < 8; o++)
{
int opo = (o + 4) % 8;
for(int t = 0; t < 8; t++)
Cost[o][t] = min(abs(opo - t), min(abs(opo + 8 - t), abs(t + 8 - opo)));
}
for(int dist = 0; dist <= DistMax; dist++)
for(int i = 0; i < Bucket[dist].size(); i++)
{
cell Node = Bucket[dist][i];
int l = Node.l, c = Node.c, o = Node.o;
if(D[l][c][o] != dist)
continue;
if(l == l2 && c == c2)
{
fout << dist << '\n';
return 0;
}
for(int t = 0; t < 8; t++)
{
int cost = Cost[o][t], nl = l + dl[t], nc = c + dc[t];
if(cost > 2 || Access[nl][nc]) continue;
int no = (t + 4) % 8;
if(cost + dist < D[nl][nc][no])
D[nl][nc][no] = cost + dist, Bucket[dist + cost].push_back({nl, nc, no});
}
}
fout << "-1\n";
return 0;
}