Cod sursa(job #2516243)

Utilizator Alex_BubBuburuzan Alexandru Alex_Bub Data 30 decembrie 2019 19:43:30
Problema Car Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.81 kb
#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;
}