Cod sursa(job #2516588)

Utilizator david.teacaDavid Stefan Teaca david.teaca Data 1 ianuarie 2020 16:32:34
Problema Car Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.51 kb
	
#include <fstream>
#include <vector>
#include <cstring>
#include <bitset>
 
using namespace std;
ofstream fout("car.out");
 
const int NMax = 500, DistMax = 5e5, oo = 1e9, BufferSize = 2e5;
 
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], pos;
bitset <NMax + 5> Access[NMax + 5];
 
char B[BufferSize + 5];
 
struct cell{int l, c, o;};
vector <cell> Bucket[DistMax + 5];
vector <pair<int, int> > G[8];
 
int Parse()
{
    int Value = 0;
 
    while(!isdigit(B[pos]))
    {
        pos++;
        if(pos == BufferSize)
            fread(B, BufferSize, 1, stdin), pos = 0;
    }
 
    while(isdigit(B[pos]))
    {
        Value = 10 * Value + B[pos] - '0';
        pos++;
 
        if(pos == BufferSize)
            fread(B, BufferSize, 1, stdin), pos = 0;
    }
    return Value;
}
 
int main()
{
    freopen("car.in", "r", stdin);
    fread(B, BufferSize, 1, stdin);
 
    N = Parse(), M = Parse(), l1 = Parse(), c1 = Parse(), l2 = Parse(), c2 = Parse();
 
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
        {
            Access[i][j] = Parse();
 
            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], no = newo[t];
 
                if(Access[nl][nc] == 0 && 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;
}