Cod sursa(job #3170411)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 17 noiembrie 2023 16:20:24
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.48 kb
#include <fstream>
#include <climits>
#include <vector>

using namespace std;

const int NMAX = 500;
const int MMAX = 500;

bool liber[2 + NMAX][2 + MMAX];
int cost[8][1 + NMAX][1 + MMAX];

// E, NE, N, NW, W, SW, S, SE
int dx[] = {0,-1,-1,-1, 0, 1, 1, 1};
int dy[] = {1, 1, 0,-1,-1,-1, 0, 1};

struct Elem
{
  int cost;
  int dir;
  int x;
  int y;

  bool operator >(const Elem& arg) const
  {
    return this->cost > arg.cost;
  }
};

vector<Elem> lista[3];

void dijkstra(int xs, int ys)
{
    for (int i = 0; i < 8; i++)
    {
        cost[i][xs][ys] = 0;
    }

    int lin = 1;

    lista[lin].push_back({0, 0, xs, ys});
    lista[lin].push_back({0, 1, xs, ys});
    lista[lin].push_back({0, 2, xs, ys});
    lista[lin].push_back({0, 3, xs, ys});
    lista[lin].push_back({0, 4, xs, ys});
    lista[lin].push_back({0, 5, xs, ys});
    lista[lin].push_back({0, 6, xs, ys});
    lista[lin].push_back({0, 7, xs, ys});

    while (!lista[0].empty()|| !lista[1].empty() || !lista[2].empty())
    {
        while (lista[lin].empty())
        {
            ++lin;
            lin %= 3;
        }

        Elem nod = lista[lin].back();

        lista[lin].pop_back();

        if (nod.cost > cost[nod.dir][nod.x][nod.y]) continue;

        for (int i = -2; i <= 2; i++)
        {
            int dir = (nod.dir + i + 8) % 8;
            Elem vecin{nod.cost + abs(i), dir, nod.x + dx[dir], nod.y + dy[dir]};

            if (liber[vecin.x][vecin.y] && vecin.cost < cost[vecin.dir][vecin.x][vecin.y])
            {
                cost[vecin.dir][vecin.x][vecin.y] = vecin.cost;
                lista[(lin + vecin.cost - nod.cost) % 3].push_back(vecin);
            }
        }
    }
}

int main()
{
    ifstream in("car.in");
    ofstream out("car.out");
    int n, m;
    int xs, ys, xf, yf;

    in >> n >> m;
    in >> xs >> ys >> xf >> yf;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            in >> liber[i][j];
            liber[i][j] = !liber[i][j];
            for (int k = 0; k < 8; k++)
            {
                cost[k][i][j] = INT_MAX;
            }
        }
    }

    dijkstra(xs, ys);

    int minim = cost[0][xf][yf];
    for (int i = 1; i < 8; i++)
    {
        if (cost[i][xf][yf] < minim)
        {
            minim = cost[i][xf][yf];
        }
    }

    if (minim == INT_MAX)
    {
        minim = -1;
    }

    out << minim << '\n';

    return 0;
}