Cod sursa(job #3327296)

Utilizator Mihai_OctMihai Octavian Mihai_Oct Data 3 decembrie 2025 10:08:34
Problema Car Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("car.in");
ofstream fout("car.out");
const int DI[] = {-1, -1, 0, 1, 1,  1,  0, -1};
const int DJ[] = { 0,  1, 1, 1, 0, -1, -1, -1};
int n, m, i, j, incI, incJ, sfI, sfJ;
int cost[502][502][8], rasp;
bool bloc[502][502];

static inline void Lee() {
    queue<tuple<int, int, int>> q[3];
    for(i = 0; i < 8; i++) {
        cost[incI][incJ][i] = 0;
        q[0].push(make_tuple(incI, incJ, i));
    }

    int coada = 0;
    while(!q[0].empty() || !q[1].empty() || !q[2].empty()) {
        while(q[coada].empty()) coada = (coada + 1) % 3;

        int i, j, d;
        tie(i, j, d) = q[coada].front();
        q[coada].pop();

        for(int rot = -3; rot < 4; rot++) {
            int costAdd = (rot < 0 ? -rot : rot);
            int dir = (d + rot + 8) % 8;

            int in = i + DI[dir];
            int jn = j + DJ[dir];

            if(!bloc[in][jn] && (1 <= in && in <= n && 1 <= jn && jn <= m)) {
                if(cost[in][jn][dir] > cost[i][j][d] + costAdd) {
                    cost[in][jn][dir] = cost[i][j][d] + costAdd;
                    q[cost[in][jn][dir] % 3].push({in, jn, dir});
                }
            }
        }
    }
}

int main() {
    fin.tie(nullptr);
    fout.tie(nullptr);

    fin >> n >> m;
    fin >> incI >> incJ;
    fin >>  sfI >>  sfJ;
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= m; j++) {
            fin >> bloc[i][j];

            for(int k = 0; k < 8; k++) {
                cost[i][j][k] = INT_MAX;
            }
        }
    }

    Lee();

    rasp = INT_MAX;
    for(i = 0; i < 8; i++) {
        if(cost[sfI][sfJ][i] != -1) rasp = min(rasp, cost[sfI][sfJ][i]);
    }
    fout << rasp;

    return 0;
}