Cod sursa(job #2516246)

Utilizator Alex_BubBuburuzan Alexandru Alex_Bub Data 30 decembrie 2019 19:51:33
Problema Car Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.98 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};
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;
}