Cod sursa(job #3172888)

Utilizator Allie28Radu Alesia Allie28 Data 21 noiembrie 2023 15:31:12
Problema Car Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.53 kb
#include <vector>
#include <queue>
#include <fstream>
#include <climits>
#include <algorithm>

using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");

struct coord {
    int i, j;
};

struct elemcoada {
    int dir;
    coord node;
};

const int LMAX = 505;
bool ai[LMAX][LMAX], used[8][LMAX][LMAX];
int dx[] = {0, 1, 1, 1, 0, -1, -1, -1}, dy[] = {-1, -1, 0, 1, 1, 1, 0, -1}, n, m;
queue<elemcoada> Q[3];
vector<vector<vector<int>>>af;

bool inside(int i, int j) {
    return i > 0 && i <= n && j > 0 && j <= m;
}

void dial(int si, int sj) {
    elemcoada aux;
    aux.node.i = si;
    aux.node.j = sj;
    for (int i = 0; i < 8; i++) {
        aux.dir = i;
        af[i][si][sj] = 0;
        Q[0].push(aux);
    }

    int nrelem, currq, dir, i, j, l, inou, jnou, cost;
    nrelem = 8;
    currq = 0;

    while (nrelem) {
        while (Q[currq].empty()) {
            currq = (currq + 1) % 3;
        }
        aux = Q[currq].front();
        Q[currq].pop();
        nrelem--;

        dir = aux.dir;
        i = aux.node.i;
        j = aux.node.j;
        if (!used[dir][i][j]) {

        l = dir - 2; //la stanga
        if (l < 0) {
            l = l + 8;
        }
        for (int cnt = 0; cnt < 5; cnt++) {
            inou = i + dy[l];
            jnou = j + dx[l];
            cost = abs(2 - cnt);
            if (inside(inou, jnou) && !used[l][inou][jnou] && ai[inou][jnou] == 0 && af[l][inou][jnou] > af[dir][i][j] + cost) {
                af[l][inou][jnou] = af[dir][i][j] + cost;
                aux.dir = l;
                aux.node.i = inou;
                aux.node.j = jnou;
                Q[cost].push(aux);
                nrelem++;
            }
            l = (l + 1) % 8;
        }
        }
    }
}

int main() {
    int si, sj, fi, fj, i, j, l;
    fin >> n >> m >> si >> sj >> fi >> fj;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            fin >> ai[i][j];
        }
    }
    for (i = 0; i <= n+1; i++) {
        ai[i][0] = ai[i][m+1] = 1;
    }
    for (j = 0; j <= m+1; j++) {
        ai[0][j] = ai[n+1][j] = 1;
    }
    af.assign(8,vector<vector<int>>(n+1,vector<int>(m+1,INT_MAX)));
    dial(si, sj);
    int mini = INT_MAX;
    for (l = 0; l < 8; l++) {
        if (af[l][fi][fj] != INT_MAX) {
            mini = min(mini, af[l][fi][fj]);
        }
    }

    if (mini == INT_MAX) {
        fout << -1;
    }
    else {
        fout << mini;
    }


    fin.close();
    fout.close();

    return 0;
}