Pagini recente » Cod sursa (job #669475) | Cod sursa (job #2607797) | Cod sursa (job #1386308) | Cod sursa (job #341481) | Cod sursa (job #2516246)
#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};
int N, M, l1, c1, l2, c2, D[NMax + 5][NMax + 5][8], newo[8];
bool Access[NMax + 5][NMax + 5];
struct cell{int l, c, o;};
vector <cell> Bucket[DistMax + 5];
vector <pair<int, int> > G[8];
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;
newo[o] = opo;
for(int t = 0, cost; t < 8; t++)
{
cost = min(abs(opo - t), min(abs(opo + 8 - t), abs(t + 8 - opo)));
if(cost < 3)
G[o].push_back({t, cost});
}
}
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(auto Next : G[o])
{
int t = Next.first, cost = Next.second;
int nl = l + dl[t], nc = c + dc[t];
if(cost > 2 || Access[nl][nc]) continue;
int no = newo[t];
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;
}