Cod sursa(job #2651145)

Utilizator pregoliStana Andrei pregoli Data 21 septembrie 2020 17:30:28
Problema Car Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.28 kb
#include <bits/stdc++.h>
#define STOP fout << '\n'; fout.close(); exit(EXIT_SUCCESS);
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
///***********************
const int NMAX = 503, OO = 2e9, ndirs = 8,
            dirI[] = {-1,-1,0,1,1,1,0,-1},
            dirJ[] = {0,1,1,1,0,-1,-1,-1};
struct Elem {
    int i, j, dir, cost;
};
queue<Elem> q0, q1;
int n, m, si, sj, fi, fj, dp[NMAX][NMAX][10];
bool a[NMAX][NMAX];

inline bool isOk(int i, int j) {
    return i >= 1 && j >= 1 && i <= n && j <= m && !a[i][j];
}

void read() {
    fin >> n >> m >> si >> sj >> fi >> fj;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            fin >> a[i][j];
            fill(dp[i][j], dp[i][j] + ndirs, OO);
        }
    for (int dir = 0; dir < ndirs; dir++)
        q0.push({.i = si, .j = sj, .dir = dir, .cost = 0});
}

void lee() {
    int i, j, k;
    Elem currE, newE;
    while (q0.size()) {
        while (q0.size()) {
            currE = q0.front();
            q0.pop();
            newE.i = currE.i + dirI[currE.dir];
            newE.j = currE.j + dirJ[currE.dir];
            newE.dir = currE.dir, newE.cost = currE.cost;
            if (isOk(newE.i, newE.j) && dp[newE.i][newE.j][newE.dir] > newE.cost) {
                dp[newE.i][newE.j][newE.dir] = newE.cost;
                q0.push(newE);
            }
            newE.cost++;
            newE.dir = (newE.dir + 1) % ndirs;
            newE.i = currE.i;
            newE.j = currE.j;
            if (isOk(newE.i, newE.j) && dp[newE.i][newE.j][newE.dir] > newE.cost) {
                dp[newE.i][newE.j][newE.dir] = newE.cost;
                q1.push(newE);
            }
            newE.dir -= 2;
            if (newE.dir < 0)
                newE.dir = ndirs - 1;
            if (isOk(newE.i, newE.j) && dp[newE.i][newE.j][newE.dir] > newE.cost) {
                dp[newE.i][newE.j][newE.dir] = newE.cost;
                q1.push(newE);
            }
        }
        while (q1.size()) {
            q0.push(q1.front());
            q1.pop();
        }
    }
}

void display() {
    int ans = *min_element(dp[fi][fj], dp[fi][fj] + ndirs);
    fout << ((ans == OO) ? -1 : ans);
}

int main() {
    read();
    lee();
    display();
    STOP
}