Cod sursa(job #3172878)

Utilizator Allie28Radu Alesia Allie28 Data 21 noiembrie 2023 15:07:51
Problema Car Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.16 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];
int af[LMAX][LMAX], dx[] = {0, 1, 1, 1, 0, -1, -1, -1}, dy[] = {-1, -1, 0, 1, 1, 1, 0, -1};
queue<elemcoada> Q[3];

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

    int nrelem, currq;
    nrelem = 8;
    currq = 0;

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

        int dir, i, j;
        dir = aux.dir;
        i = aux.node.i;
        j = aux.node.j;

        int l = dir - 2; //la stanga
        if (l < 0) {
            l = l + 8;
        }
        for (int cnt = 0; cnt < 5; cnt++) {
            int inou, jnou, cost;
            inou = i + dy[l];
            jnou = j + dx[l];
            cost = abs(2 - cnt);
            if (ai[inou][jnou] == 0 && af[inou][jnou] > af[i][j] + cost) {
                af[inou][jnou] = af[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 n, m, si, sj, fi, fj;
    fin >> n >> m >> si >> sj >> fi >> fj;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            fin >> ai[i][j];
            af[i][j] = INT_MAX;
        }
    }
    for (int i = 0; i <= n+1; i++) {
        ai[i][0] = ai[i][m+1] = 1;
    }
    for (int j = 0; j <= m+1; j++) {
        ai[0][j] = ai[n+1][j] = 1;
    }
    dial(si, sj);
    if (af[fi][fj] == INT_MAX) {
        fout << -1;
    }
    else {
        fout << af[fi][fj];
    }


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

    return 0;
}